Data Structures

CSI33     D01 (61239)

Monday, Wednesday, 2:00 pm-3:50 pm, room CP 320
 

 
Date Class Materials HW assignment
09/29 No in-person meeting today, asynchronous online class;

Please follow the study plan:
1) watch this video: Algorithm Analysis (continue with Binary Search) ~12 mins long
2) Grab the handout, and work on the three problems on one side of it with the help of this video: Handout, problems 1-3 on one side
3) Flip the page of the handout over and work on the last problem.
Do items 1) and 2) on your own: copy the program, run it, see what the function returns when n = 1, when n = 2, and when n=10. Write down the results.
Then proceed with this video that is working on items 3) - 5)

The handout: CSI33-Lecture05InClassPractice2.pdf
Suggested exercise (for practice, not for grade):
1) Look at your implementation of the Selection Sort.
What assymptotic running time does it have?
Here is the running time analysis of the Selection Sort.
2) estimate the run-time complexity of the following block of code:
# n is a positive integer
s = 0
for i in range(n):
      for j in range(10):
            s += 1
3) estimate the run-time complexity of the following block of code:
# the program finds a square root of n, if the answer is an integer value:
n = int(input("Enter a positive integer:"))
assert n >= 1
i = 1
while i * i <= n:
      if i * i == n:
            return i
      else: i+= 1
return "not an integer"
09/28 Sections 1.1, 1.2, and 1.3

Lecture slides - part 1, Lecture slides - part 2

In-class work: CSI33-Lecture05Handout.pdf, CSI33-Lecture05InClassPractice2.pdf
Solutions: CSI33-Lecture05InClassPractice2-answers.pdf

Additional materials: BinarySearchIllustrated.pdf

Additional resources: Check out this simple explanation of big-O notation:
https://medium.freecodecamp.org/big-o-notation-simply-explained-with-illustrations-and-video-87d5a71c0174
HW 3 (due date: Thursday, 10/06):
Programming Exercise #9 , page 38 from Textbook (write it in Python)
comments:
1) Write the program in Python, do not use any built-in stuctures other than Python list
2) function squeeze should not modify the original list; instead, it should return a new list.
3) pay attention to everything you are asked to do!

Suggested exercises (for practice, not for grade):
1) Look at the example of a simple statistics program (interface) on page 15 in the textbook
2) True/False questions: p. 33 / 4-6, 9, 10 - not for grade
3) Multiple Choice questions: pp.34-35 / 1-6, 10 - not for grade
    Solutions: Chapter1solsTFMConly.pdf
4) Short-answer questions: p. 36 / 8 - not for grade
    Solution: Chapter1ShortAnswerQuestions.pdf
5) read about docstring conventions at http://www.python.org/dev/peps/pep-0257/
6) Watch a video about O, Ω, and Θ notations: https://youtu.be/6Ol2JbwoJp0
Homeworks, Midterm Exam and Final Exam warning:
The homework, midterm exam, and final exam work must be solely your work.
They are not for group work, they are not to be looked for the solutions in online resources.
If I notice that your homework is similar to somebody else in our class, both parties' homework score will be zero (same for Midterm and Final Exam).
If I notice that you found a solution in online resources, your score will be zero as well.
Both cases, copying from somebody or finding and solution in online resources, are academic dishonesty.
You will be given first and last warning.
If I notice anything hapenning again, you will be reported to the chairperson and you may end up with a failing grade for this class.

Academic Integrity
Academic dishonesty (such as plagiarism and cheating) is prohibited at Bronx Community College and is punishable by penalties, including failing grades, dismissal and expulsion. For additional information and the full policy on Academic Integrity, please consult the BCC College Catalog.

Tutoring Lab for CSI 30, 31, 32, 33, 35:
Online: (visit Blackboard -> BCC online tutoring at the top right corner)
      Monday 11 am - 2 pm
      Tuesday: 11 am - 3 pm

In-Person:
(Appointments are required for in-person support via  WCOnline )
      Wednesday: 2 pm - 8 pm
      Thursday: 11 am - 2 pm; 6 pm - 8 pm
09/21 Topics to be covered:
Chapter 8: Sections 8.1 Introduction and 8.2 C++ History and Background
Chapter 10: Sections 10.1 Introduction, 10.2 C++ pointers, and 10.3 Dynamic Arrays

Lecture slides

Practice questions
Answer to question 1 (picture)
Suggested exercises (for practice, not for grade):
1) True-False questions: p. 396 / 3, 4,
2) Multiple-Choice questions: p. 397 / 1, 2, 3, 5
3) Short-Answer questions: p. 399 / 5, 6
Solutions/Answers: Chapter10-questionsAnswers.pdf

More practice with pointers: http://condor.depaul.edu/ntomuro/courses/309/notes/pointer_exercises.html
09/19 Today we will refresh our memory about classes in Python and C++. We will be working on the class Complex of a complex number in its rectangular form (a+bi)

Lecture slides


Picture of the smart lock for the HW assignment:
HW 2 (due date: Wednesday, 09/28):
White a class that will emulate a smart door lock with pin pad.
Name the class SmartLock and see the features it should have:
  • every smart lock comes with an admin pin code, i.e. every instance of the class SmartLock should have admin's pin code as a required parameter.
  • the length of any pin code is only four digits (not more, not less)
  • the smart lock can have more than one pin code that will open the door. For example: the admin code, the code for kids, the code for in-laws, the code for cleaning crew, etc.
  • any smart lock can store up to 10 pin codes (not more)
  • to enter a new pin-code, define a method AddNewPinCode() that should have two parameters: admin's pin code (for verification) and new pin code
  • the smart lock doesn't need to store information about pin code's dedication (for kids or for in-laws, it doesn't matter to the lock)
  • any pin code, except for the admin's pin code, can be removed, hence define a method RemovePinCode() that should take two parameters: admin's pin code (for verification) and the pin code to be removed
  • The lock has only two states: OPEN and LOCKED, hence think about having a "state" attribute to store the state of the lock
  • define a method EnterPin() that takes only one parameter: a pin code. If the pin code is one of the valid ones, the door lock should change it's state to the opposite one, i.e. if it was locked, it should become ulocked, and vice versa, if it was unlocked, it should become locked.
  • define a method Lock(), that should lock the smart lock independently at what state was it in
  • Finally, define a method CheckState() that doesn't take any parameters, but returns the "state" of the lock to us - whether it is locked or not (you can either return True or False, or , 0 or 1, where True(1) is for "LOCKED" and False(0) for "UNLOCKED")

    Declare the class in a header file .h, put all the necessary definitions into the implementation .cpp file (if you find it necessary), finally the test code put into a separate .cpp file. Send all the files to me as attachments to an email with subject HW 2 in the subject field.
09/14 We worked on three algorithms: linear search, binary search (in both, Python and C++), and selection sort (in Python)

Lecture slides
Handouts / in-class materials: Selection Sort,
binarySearch.py

the programs we did in class:
linearSearch.py, linearBinarySearch.cpp, SelectionSort2.py
HW 1 (due date: Wednesday, 09/21):
implement the Selection sort in C++.
In your implementation:
* define a function SelectionSort that takes two formal parameters: the array and its size,
* assume that the capacity of the array is 100 elements,
* you may also assume that we are working only with integer values, but you can work with decimal numbers as well, just be consistent!

Comments: Send your cpp file as attachment to an email with subject HW 1 in the subject field.
09/12 Hello and welcome to CSI 33 class.
I plan to spend week and a half to two weeks on Python and C++ languages review.
Therefore, make sure that you have both compilers available and ready to be used.

If we don't have the compilers installed in our lab, we can use the following online compilers for now:
Python at replit or Python at OnlineGDB
C++

Announcements:
First two chapters of the book are available through e-reserves:
http://bcc-cuny.libguides.com/er.php?b=c
Choose CSI33 from the list
HW 0 (due date: Wednesday, 09/15):
1) order the textbook

2) get the Python interpreter and C++ compiler, make sure they are working