Material covered:

1. Why do we need analysis of algorithms and advanced data structures?

• History of computing -- from hardware to visual programming in very high level languages
• High performance computing
• TOP 500 -- list of most powerfull computers in the world
• Problems that lead to the need of extra efficient algorithms

2. Introductory steps

• Insertion sort
• Analysis of the insertion sort
• • best case performance
  • worst case performance
  • average performace
• Merge sort
• Divide-and-conquer algorithms
• Analysis of the merge sort
• • best case performance
  • worst case performance
  • average performace

3. Analysis of algorithms == what does matter?

• What is difficult and what is easy?
• The case of iterative solvers for systems of linear eqations
• The case of solvers for systems of nonlinear algebraic equations

4. Growth functions

• Θ
• O
• Ω
• o
• ω

5. Solving recurrences

• Substitution method
• Recursion-tree method
• Master theorem method

6. Probabilistics analysis and randomized algorithms

• Probabilistic analysis == what do we know about the input data?
• Randomized algorithms == how can we make data "look" randomized?
• Algorithms for permuting data

7. Quicksort and its flavors

• General idea behind Quicksort
• Performance and its dependence on pivot selection
• Pivot selection strategies
• • leftmost pivot
  • median of three pivot
  • random pivot
  • randomization of data combined with leftmost pivot

9. Heapsort

• Heap == definition
• Maintaining the heap property == procedure heapify (max and min)
• Building a heap
• Heapsort algorithm
• Priority queues

10. Non-comparison-based sorting

• Proof that comparison-based sorting must be O(nlogn)
• Counting sort == for integers only
• Radix sort == old mechanical sorting method == how to implement it?
• Bucket sort == limited application, but interesting technique

11. Medians and order statistics

• The problem
• Minimum and maximum
• Selection in linear time
• Weird algorithm that is still a mystery

12. Elementary data structures

• Stacks and queues
  • Stacks and operations on them
  • Queues and operations on them
  • Asbtract data object vs. its implementation
• Linked lists
  • Linked lists and operations on them
  • Doubly linked lists
  • Sentinels
  • Implementing pointers and linked lists
  • Implementing binary trees
  • Implementing trees with unbounded branching
• Hash tables
  • Need for hash tables
  • Direct address tables
  • Hash tables
    • Collisions and collision resolution by chaining
    • Hash funtions and their quality
      • The division method
      • The multiplication method
      • Universal hashing
    • Open addressing
      • When open addressing is an option?
      • Open addressing methods
        • Linear probing
        • Quadratic probing
        • Double hashing
        • Perfect hashing

13. Lecture by Professor J. Thomas -- Introduction to Networking (Data Structures and Algorithms)

Homework 1

• Part I Compare the performance of insertion sort and merge sort for a random sequence of numbers.
• Part II Compare the performance of insertion sort and merge sort for a sorted sequence of numbers.
• Part III Compare the performance of insertion sort and merge sort for a reverse-sorted sequence of numbers.

As the final product I want to receive a paper / report (which in form follows format discussed in class) that summarizes and discusses the results of your experimental work. Homework is to be submitted to me via e-mail . Due by Sunday, September 5 ^th before I start grading it on that day (I will definitely not start grading before 8:00 AM).

Homework 2

• Textbook, page 67, problems 4.1-1 and 4.1-5

Due by Thursday, September 16 ^th at class time.

Homework 3

• The aim of this assignment is to compare performance of Mergesort and Insertion sort when data is almost sorted.
• More precisely, assume that n elements are already sorted and that subsequently k elements need to be in-sorted into the already sorted data.
• For this scenario compare the performance of Mergesort and Insertion Sort for varying values of n and n .

As the final product I want again to receive a paper / report (which in form follows format discussed in class) that summarizes and discusses the results of your experimental work. This is to be a report that is separate form the report that you have submitted in Homework 1. Homework is to be submitted to me via e-mail . Due by Sunday, September 19 ^th before I start grading it on that day (I will definitely not start grading before 8:00 AM).

Homework 4

• Textbook, page 72, problems 4.2-1, 4.2-2
• Textbook, page 75, problems 4.3-1, 4.3-2, 4.3-3

Due by Thursday, September 23 ^rd at class time.

Homework 5

• The aim of this assignment is to develop an "ultimate Mergesort."
• It is claimed in the textbook that applying Insertion Sort in the final stages of Mergesort (when there are very few elements left in the divide-stage) can speed-up the overall performance of Mergesort. Let us verify this claim:
  • Is this really the case that it works in computational practice?
  • For a given n what is the best k when the process should switch to Insert-sorting?
  • If n changes (e.g. increases), does this affect the value of k when the switch should be made?
• As the result, you should come up with the best possible Merge-sort (for your programming language, implementation details, computer on which you run experiments etc.

As the final product I want again to receive a paper / report that summarizes and discusses the results of your experimental work. This is to be a report that is separate form the reports that you have submitted in Homework assignments 1 and 3. Homework is to be submitted to me via e-mail . Due by Friday, October 1 ^th at 12 Noon.

Homework 6

• Implement Quicksort; perform experiments comparing its performance depending on the pivot selection strategy. Utilize at least the following approaches to pivot selection:
• • leftmost pivot
  • random pivot
  • median of three pivot (left + right + middle)
  • median of three random elements pivot
  • randomize data and leftmost pivot

As the final product I want again to receive a paper / report that summarizes and discusses the results of your experimental work. This is to be a report that is separate form the reports that you have submitted in earlier Homework assignments. Homework is to be submitted to me via e-mail . Due by Saturday, October 9^th at 23:55 (Tulsa time).

Homework 7

• Aparently, the performance of Quicksort can be substantially improved the same way as the performance of Mergesort -- when in the final stages of the algorithm the recursion is replaced by inserion sort. Experimentally verify this hypothesis. Use the best pivoting strategy established in Homework 6.

As the final product I want again to receive a paper / report that summarizes and discusses the results of your experimental work. This is to be a report that is separate form the reports that you have submitted in earlier Homework assignments. Homework is to be submitted to me via e-mail . Due by Saturday, October 16^th at 23:55 (Tulsa time).

Homework 8

• Implement Heapsort; perform experiments comparing its performance with that of the Ultimate Mergesort and Ultimate Qicksort (for random, sorted and reverse sorted data).

As the final product I want again to receive a paper / report that summarizes and discusses the results of your experimental work. This is to be a report that is separate form the reports that you have submitted in earlier Homework assignments. Homework is to be submitted to me via e-mail . Due by Tuesday, October 26^th at 23:55 (Tulsa time).

Homework 9

• Implement teaching-aids for two concepts:
  • stack
  • queue
• These teching-aids should have nice graphical design to entice young computer scientists to learn

As the final product I want executable codes that I will just fire-up and play with. Homework is to be submitted to me via e-mail . Due by Thursday, November 10^th at 23:55 (Tulsa time).

Reading assignment , textbook pages xiii-252

Back to the syllabus page