Data Structures

CSI33      D01 (45383)

Monday, Wednesday, 12:00 pm-1:50 pm, room CP 320
 

 
Date Class Materials HW assignment
Week 6

Summarize the data structures we explored so far with the run-time efficiency of common operations!!!

Midterm Exam will be on Wednesday, March 13th
 
02/27 Sections 5.3-5.5

Lecture slides: CSI33-lecture09.pdf

programs (from the book): MyQueue.py, palindrome.py

In-class work: see the lecture slides, CabCompany.pdf, TestingCab.py
Solution: CabCompany.py

Self-study:
time-driven simulation: simulation.py, CheckerSim.py
Event-driven simulation: simulationEventDriven.py, CheckerSimEventDriven.py
 
HW9 (due date: Wednesday, 03/07)

programming exercise: p. 184 / 4
02/25 Quiz 3 (covers Chapters 3 and 4)

Sections 5.1-5.2

Lecture slides: CSI33-lecture08.pdf

programs (from the book): Stack.py, parensBalance2.py

In-class assignment: see lectures slides.
Solutions/answers: In-classWorkAnswers.pdf, Stackunittesting.py

Check out these useful videos:
Infix to Postifx:
https://www.youtube.com/watch?v=rA0x7b4YiMI
Infix to Prefix:
https://www.youtube.com/watch?v=fUxnb5eTRS0
 
HW8 (due date: Monday, 03/04)
programming exercise: p. 184 / 3 (use Stack to evaluate the post-fix expression as shown in lecuture slides)

Suggested exercises:
1) True-False questions: p. 181 / 1-4
2) Multiple-Choice questions: p. 182 / 1-5
3) Short-Answer questions: p. 183 / 1

Answers/Solutions: Chapter5-questionsAnswers-part1.pdf, Chapter5-questionsAnswers-part2.pdf
Week 4
Now you can see your class grades here: https://goo.gl/ugzxVm
Use the last 4 digits of your school ID to find your record  
02/20 Sections 4.4 - 4.5, 4.7

Lecture slides: CSI33-lecture07.pdf

Programs: ListNode.py, LList.py

In-class work: see the last slide in the lecture slides
Solutions: Section4_6InClassWork.py (work with LList),
Fibonacci numbers generator (2 versions): Section4_6InClassWorkGenerator.py, Section4_6InClassWorkGenerator.py Which version do you like better?
HW7 (due date: Wednesday, 10/03)
1) programming exercises: p. 152 / 1, 3 (do both in one file, LList.py)

Suggested exercises:
1) True-False questions: p. 148 / 1, 2, 4, 5
2) Multiple-Choice questions: p. 149 / 1-4
3) take a look at two versions of __copy__ method for LList class's implementation on page 132.
Solutions/answers: Chapter4-questionsAnswersSuggestedProblems.pdf
Week 3

Note that on Tuesday, February 12th the college is closed - Lincoln's birthday
on Monday, February 18th the college is closed - President's day

 
02/13 Sections 4.2-4.3

Quiz 2 today

Lecture slides: CSI33-lecture06.pdf

Programs: Section4_2example.py, ListNode.py
For in-class work: Sections4_1-4_3InClassWork.py, Section4_2example2.py

In-class work: see lecture slides (the last two slides) and use this file: problems1-2
Answers:
    problems 1-2: ListNode_classwork.py, Sections4_1-4_3InClassWorkProblems1-2.py;
    problems 3-4: In-classWorkProblems3_4.pdf
HW6 (due date: Wednesday, 02/20)

Programming assignment: Let's think about doubly-linked lists. Define a class ListNode2, with three attributes: item, leftL, and rightL.
Left link points to the previous node in the list, right link points to the next node in the list.
You can also add the display method to this class (like we did it in class for the ListNode class).
Then test your class.
For example, create a linked list of 5 values: 34, 1, 23, 7, and 10. Display it. Then insert new value, say 8 between 34 and 1 (this time you will have to take care of links pointing to the previous and next node), display the resulting list. Then delete an element, say 7, update the links and display the new list.
Use this draft: ListNode2_forStudents.py


Suggested exercises
(not for grade, but highly recommended):
1) Short-Answer questions: p. 151 / 2
Answers: Chapter4-questionsAnswers.pdf
02/11 Sections 3.5-3.6

Lecture slides: CSI33-lecture05.pdf

Here is a link to time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython: https://wiki.python.org/moin/TimeComplexity

Quiz 2 will be on Wednesday, February 13th and will be based on Chapters 2 and 3.
HW5 (due date: Wednesday, 02/20)
programming exercise: p. 104 / 9
See suggested specification with some code here:
a simple version (do not store the contents of each pile, only the top card): Chapter3-prog9SolitaireSpecs-easy.py


Suggested exercises
(not for grade, but highly recommended):
1) True-False questions: p. 100 / 8, 12
2) Multiple choice questions: p. 101 / 1, 3, 4, 5, 6, 8
3) Short-answer questions: p.102 / 3

Solutions: Chapter3-questionsAnswers-part1.pdf, Chapter3-questionsAnswers-part2.pdf

Week 2
 
02/06 Sections 3.1-3.4

Quiz 1 today (based on Chapter 1)

Lecture slides: CSI33-lecture04.pdf
HW2 discussion: SelectionSortAnalysis

On this page you can find the link to the compressed file with all the codes from the book:
http://www.fbeedle.com/content/data-structures-and-algorithms-using-python-and-c

more programs (from the book):
CardADT.py,
Card.py (different from previous lecture meeting), Deck.py, Hand.py, TestDeck.py, TestCards.py

If you want to find out how to play Bridge:
rules: http://www.acbl.org/learn_page/how-to-play-bridge/
video: https://www.youtube.com/watch?v=Tyd7KlsRYO4
another video: https://www.youtube.com/watch?v=9yzS_26fICk

In-class work: see lecture slides (last few slides)
Solutions: in-classWork.py 
HW4 (due date: Wednesday, 02/13)

1) Finish implementing the program discussed in class (in-class work, second assignment).
comment: note that at this level you should define classes (for example, for player, for scoring and so forth) where appropriate, also don't forget documentation (both inner comments that start with # and docstrings)! The program must use the classes Card and Deck we defined in class.

2) Programming Exercises: p 103 / 1, 2, 3- all of these exercises should be implemented in one file Deck.py
Test all the operations, send the tests with your HW submission!


Suggested exercises
(not for grade, but highly recommended):
1) True-False questions: p. 100 / 2, 3, 6
2) Short-answer questions: p.102 / 1, 2

Solutions: Chapter3-questionsAnswers-part1.pdf
02/04 Sections 2.1-2.3, and 2.6 from the book.

Lecture slides: CSI33-lecture03.pdf

Programs:
cardADT.py, test_cardADT.py,
Card-spec.py,
Card.py, testCard.py, unitTestingCard.py

In-class work: start working on the HW assignment
HW3 (due date: Monday, 02/11)

Write unit tests to test the methods suit, suitName and rankNameof Card class

See the Chapter2-unitTestingCardHW.py

Week 1
 
01/30 Section 1.3 Algorithm Analysis

Lecture slides: CSI33-lecture02.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

In-class work: lecture02InClassPractice.pdf
Solutions: lecture02InClassPracticeSols.pdf
HW2 (due date: Wednesday, 02/06):

1) True/False questions: p. 33 / 4-6, 9, 10 - not for grade
2) Multiple Choice questions: pp.34-35 / 1-6, 10 - not for grade

Solutions: Chapter1solsTFMConly.pdf

3) Short-answer questions: p. 36 / 8 - not for grade
Solution: Chapter1ShortAnswerQuestions.pdf

4) Write a program that has both Linear Search and Binary Search algorithms implemented defined as two seprate functions.
Run each of the algorithms on the list of integers from 0 to 999999 and time them on three different numbers to search for: 10, 499999, and 999999. At the end your program should print the results.
Here is a draft/skeleton of the program: hwAssignment-twoSearches.py

5) Programming Exercises: p. 37-38 / 3, 9
Comments:
* Programming exercise 3 asks you to implement Selection Sort algorithm.
See my comments here: here and
video (about 10 mins) presenting visualization of Selection Sort: https://www.youtube.com/watch?v=f8hXR_Hvybo

* In programming exercise 9 you are not to use the built-in set type.

Reminder: don't forget to put specification for each of the functions you are defining as well as to use internal comments (that start with #)
01/28 Sections 1.1, 1.2

Lecture slides: CSI33-lecture01.pdf

In-class work: lecture01-handout.pdf
Solutions: lecture01-handoutSols.pdf

We watched a video about O, Ω, and Θ notations: https://youtu.be/6Ol2JbwoJp0

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
HW1 (due date: Sunday, 02/03):
1) read Sections 1.1-1.2

2) read about docstring conventions at http://www.python.org/dev/peps/pep-0257/

3) get the book