Data Structures

CSI33
D01 70855
Monday, Wednesday, 12:00pm-1:50pm, room CPH 320

 
  • HW21 - Last HW assignment!!! (due date: Thursday, 05/07)

    1) Short-Answer questions: p. 424 / 1, 2
    Solutions: Chapter11questionsAnswers.pdf


    2) Programming exercise: p. 424 / 2
        here is the code to check that your program works correctly: Chapter11-testLList2.cpp
    Solution: Chapter11-prog2-ListNode.h, Chapter11-prog2-LList.h, Chapter11-prog2-LList.cpp

    3) Programming exercise: p. 442 / 2
    Solution: Queue.h, Queue.template, test_Queue.cpp

    Suggested exercises (for practice, not for grade):

    1) True-False questions: p. 440 / 1, 2, 5

    2) Multiple-Choice questions: p. 440-441 / 1, 2, 4

  • HW20 (due date: Monday, 05/04)

    1) Programming exercise: p. 400 / 4

    Suggested exercises (for practice, not for grade):

    1) True-False questions: p. 422 / 1, 2, 5

    2) Multiple-Choice questions: p. 423 / 1, 2, 4
    Solutions: Chapter11questionsAnswers.pdf


  • HW19 (due date: Wednesday, 04/29)

    1) Short-Answer questions: p. 399 / 5
    Solutions: Chapter10-questionsAnswers.pdf

  • HW18 (due date: Monday, 04/27)

    1) Programming Exercise: p. 352 / 3

    2) Short-Answer questions: p. 399 / 6
    Solutions: Chapter10-questionsAnswers.pdf


    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
    Solutions: Chapter10-questionsAnswers.pdf

  • HW17 (due date: Wednesday, 04/09)

    1) Read about macros on page 302 and see example (macro.cpp)

    2) read sections 8.17.2 and 8.17.3

    3) programming exercise: page 317/ 8-9
    Solution: searches.h, searches.cpp, test_searches.cpp,

    4) Short Answer questions: page 351/4
    Solution: Chapter9-questionsAnswers.pdf

    Suggested exercises
    (for practice, not for grade):

    1) look through the True/False and Multiple choice questions

    2) Use our Python code (mergeSort.py) and write the definition of Merge Sort. Use the following files to put Selection sort (selection.cpp) and Merge sort into: sort.h, sort.cpp, and then use these ones to test them: test_sort.cpp, test_sort2.cpp.

  • HW16 (due date: Monday, 04/20)
    1) programming exercise: page 316/ 6
    Solution: Chapter8-prog6.cpp

  • HW15 (due date: Wednesday, 04/15)
    1) Read the beginning of Section 8.2 (pages 256-257),

    2) programming exercises: page 316/ 1, 2, 3, 4
    for programming exercise 2, here is the link to the slides that give the algorithm for it (starting from slide 53): CSI30-Ch3Section1part2.pdf
    Solutions: Chapter8-prog1.cpp, Chapter8-prog2.cpp, Chapter8-prog3.cpp, Chapter8-prog4.cpp

  • HW14 (due date: Wednesday, 04/15 - corrected)
    1)AVL trees (Short Answer questions): page 481 / 4-11,
    Solution: Chapter13-AVL-answers.pdf

    2) Look through the AVL code and lecture slides - understand how the rotations are done. Finish up the AVL.py code.
    Comments    : you can use the following code for testing/seeing what is happenning(just add it to your program) helpForAVL.py
    Solution: AVLTree-completeImproved.py

  • HW13 (due date: Wednesday, 04/01)
    programming exercises: p. 248 / 2, 3, 5
    Solutions: BSTenhanced.py, BSTenhanced-using.py

  • HW12 (due date: Monday, 03/30)
    1) Short-Answer questions: p. 248 / 6
    Solution: Chapter7-questionsAnswers.pdf

    2) Write unit tests for class BST to test insert_rec and find method, by doing the following:
    Insert the following elements, one by one into a tree: 7, 3, 8, 2, 5, 9, then by using BST's method asList compare the produced by that method list with list [2,3,5,7,8,9] corrected on 03/31- this is one unit test for insert_rec method.
    To test the find method: create the same BST as above, and find 8, 2, 9, and 5; compare the result with the numbers themselves. Then try to find 11, 1, and 4 and compare the result of each search with None.
    Solution: lkj

    3) Using method asList define method arrayRepresentation that would convert a BST tree from linked list representation to array representation (recall that if a node doesn't have right/left node, it is replaced by None - see lecture slides) . For testing you can use lecture 12, slide 27 example.
    Solution: BSTtoArray.py

  • HW11 (due date: Monday, 03/23)
    1) programming exercises: p. 216 / 5
    Solution: Chapter6-prog5.py

  • HW10 (due date: Friday, 03/20)
    1) What list is returned by anagrams("word")?

    2) Trace recPower(4,8) and figure out exactly how many multiplications it does.

    3) Short-Answer questions: p. 214 / 5
    Solutions for 1-3: Chapter6Answers.pdf

    4) programming exercises: p. 215-216 / 1, 9
    Comment to #9: Try to trace the recursive calls when calculating C46: you will see a lot of repititions of the same calculation. Can you think of a way to eliminate those repetitions, as was done with fib?
    Solutions: Chapter6-prog9.py (note that this version is not efficient, repetitions in recursive version + inefficient formula use)

    Suggested exercises
    (for practice, not for grade):
    1) True-False questions: p. 212 / 1, 2, 3, 6
    2) Multiple-Choice questions: p. 213 / 1, 4, 5, 6
    Solutions: Chapter6-questionsAnswers-part1.pdf

  • HW9 (due date: Monday, 03/16)

    1) programming exercise: p. 184 / 4
    Solution: Chapter5-prog4-easyVersion.py

    2) look at the midterm exam sample

  • HW8 (due date: Wednesday, 03/11)
    0) Look through the solutions to the previous class's in-class work.

    1) Short-Answer questions: p. 183 / 1
    Solution: Chapter5-questionsAnswers-part2.pdf

    2) programming exercise: p. 184 / 3
    Solution: Chapter5-prog3.py

    Suggested exercises:
    1) True-False questions: p. 181 / 1-4
    2) Multiple-Choice questions: p. 182 / 1-5
    Solutions: Chapter5-questionsAnswers-part1.pdf

  • HW7 (due date: Monday, 03/09)
    1) programming exercises: p. 152 / 1, 3
    Solution: Chapter4-prog1_3LList.py

    2) take a look at two versions of __copy__ method for LList class's implementation on page 132.

    Suggested exercises:
    1) True-False questions: p. 148 / 1, 2, 4, 5
    2) Multiple-Choice questions: p. 149 / 1-4
    Solutions/answers: Chapter4-questionsAnswers.pdf

  • HW6 (due date: Wednesday, 03/04 extended to Friday, 03/06)
    1) Short-Answer questions: p. 151 / 2
    Solutions/answers:Chapter4-questionsAnswers.pdf

    2) 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 and element, update the links and display the new list.
    Solution: ListNode2.py

  • HW5 (due date: Monday, 03/02 extended to Wednesday, 03/04)
    1) Short-answer questions: p.102 / 3
    Solutions/answers: Chapter3-questionsAnswers-part2.pdf

    2) programming exercise: p. 104 / 9
    See suggested specification with some code here: Chapter3-prog9SolitaireSpecs.py, a simpler version: Chapter3-prog9SolitaireSpecs-easy.py
    Solution: Solitaire.py, Chapter3-prog9SolitaireStats.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

  • HW4 (due date: Friday, 02/20)
    1) read sections 2.3 and 2.4 and skim through 2.6, as well as 3.1-3.4

    2) Programming Exercises: p 103 / 1, 2, 3 (don't forget to test all the operations, send the tests with your HW submission) - all of these exercises should be implemented in one file Deck.py
    Solution: (updted as of 03/06) Chapter3-progs1-3DeckModification.py, Chapter3-progs1-3DeckModification2.py (a better version)

    3) Finish implementing the program discussed in class (in-class work, second assignment). Here the description: Write a program that will implement the card game described below (with the use of classes Card and Deck).

    The game is played by two players. A deck of cards is put face down and one of the players draws a random card from the deck, both players see the suit and the card is put back into a random place into the deck. The suit on that card is the trump suit.

    At each turn, the players grab one card each from the top of the deck (in order, so there is a person who goes first and there is a person who goes second). They turn them face up and place on the table.
    If both cards have the same suit, then the player with the highest ranked card wins this turn, takes this pair of cards and places them aside, but near him/her.
    If cards have different suits, then the person with a trump card wins his turn, takes this pair of cards and places them aside, but near him/her.
    If the cards have different suits and none of them is a trump, then it is a tie, the cards are discarded.

    The game ends when there is no more cards in the deck.

    The person with more cards wins.

    You program must print each turn, by showing the both players cards and telling who won this turn. Then at the end, it should say who won the game and how many cards each player has.
    Solution: Card.py, Deck.py, Chapter4-game.py, Chapter4-gameRun.py (this is the one to run)

    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/Answers: Chapter3-questionsAnswers-part1.pdf

  • HW3 (due date: Monday, 02/16)

    1)Write unit tests to test the functions/methods suit, suitName and rankName for Card.py
    Solution: Card.py, Chapter1-unitTestingCard.py
    2) page 71 - programming exercise 3
    Solution: Chapter3-DeckNaive.py

  • HW2 (due date: Wednesday, 02/11), given at lecture 2:

    1) Short-answer questions: p. 36 / 8
    Answers: Chapter1ShortAnswerQuestions.pdf

    2) Write a program that has both Linear Search and Binary Search algorithms implemented (should be defined as two 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
    Solution: Chapter1-twoSearches.py

    3) Programming Exercises: p. 37-38 / 3, 9

    See comments about programming exercise 3 here or in a handout I distributed in class, and
    Video is here (about 10 mins): https://www.youtube.com/watch?v=f8hXR_Hvybo
    Solutions: Chapter1-SelectionSort.py, Chapter1-prog9-sqeezer.py

    Suggested exercises
    (not for grade, but highly recommended):
    1) True/False questions: p. 33 / 4-6, 9, 10
    2) Multiple Choice questions: pp.34-35 / 1-6, 10
    Solutions (answers): Chapter1solsTFMConly.pdf

  • HW1 (due date: Monday, 02/09), given at lecture 1:
    1) read Sections 1.1-1.3 (up to Linear Search)

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

    3) order the book

    To install Eclipse:

    (due date: Wednesday, 01/29), given at lecture 1:
    1) Visit http://www.python.org/download/, download and install Python 3

    2) Visit http://www.eclipse.org/downloads/index.php, download and install Eclipse IDE for C++ Developers

    3) Follow directions at http://www.vogella.com/tutorials/Eclipse/article.html up until section 6.4 (don't read that section - it is for Java programming)
    you can get the latest Java Runtime Environment here: http://www.oracle.com/technetwork/java/javase/downloads/java-se-jre-7-download-432155.html

    4) Follow directions at http://www.vogella.com/tutorials/Python/article.html up to section 4 (you can read further - it is up to you, but we will go over it in our next class)