Data Structures

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

Here is the list of suggested Final Projects:
  • Recursion: Kosh Snowflake
    (see our book, page 219 exercise 10)

  • Recursion: C-curve
    (see our book, page 220 exercise 11)

  • Cryptography: encoding and decoding messaages using the Vignere Cipher - taken

    Here is the information about it (in the beginning the general introduction along with description of two easier algorithms is given, and the Vignere Cipher's description is given at the end): cryptography.pdf (I will try to get a better quality shortly)
    This project is already taken by a students.
    Let me know if you are interested in Cryptography - I will find another one for you.

  • Polynomials in C++ using dynamic arrays
    (see page 352, exercise 6 + page 400, exercise 3)

  • Implement Quicksort using either Python or C++
    (using the given algorithm)
    The worst-case running time for this sort is still Theta(n^2), but on average it runs in Theta(n log n) time. It's randomized version works even better.

    the original QuickSort Algorithm: QuickSort-page1.jpg, QuickSort-page2.jpg, QuickSort-page3.jpg, and

    the Randomized QuickSort: RandomizedQuickSort-page1.jpg, RandomizedQuickSort-page2.jpg

  • Implement Radix sort using either Python or C++
    (using the given algorithm)

    Radix sort is called a linear sort (you can read about it in the information provided in the pictures).

    Here is the information and algorithm for the Radix Sort: RadixSort-page1.jpg, RadixSort-page2.jpg, and

    Here is the algorithm for one of the stable sorts: CountingSort-page1.jpg, CountingSort-page2.jpg, CountingSort-page3.jpg

  • write an AVL class using C++, add ability to display the tree

  • Complete the AVL tree class (the one that we wrote in Python) with the rest of operations our BST class has, and add the ability to display the tree either using graphics or using shell nicely. This project should be done in Python.

  • Here is a pdf file with the list of the projects: CSI33FinalProjects.pdf
    - projects 3, 4 and 9 are taken