CS 5413 DATA STRUCTURES AND ALGORITHMS II

GROUPS and THEIR PROJECTS

• Client Componentn of the e-Travel Project Karthik Chinnayan Muthukumaraswamy, Al Sarraf and Vijay Kumar Damera
• Agent-based Negotiations in e-Commerce, Yu Wang, Haihong Ma, Huawen Xu
• GIS Component for the e-Travel Project, Tao Feng, Juan Du and Sije Yu
  
• Content Personalization for the e-Travel Project, Hamid Ghoratolaeyan and Imran Afzal
  
• Indexing Componentn of the e-Travel Project, Steve Williams, Patrick Harrington and Jimmy Wright
  
• Agent Negotiations, Parakh Garima, Sandhya Rani Peddabachigari

Material covered:

1. Group project selection and discussion. Completed during class time on August 29^th.

2. Initial project presentations by all groups. Delivered September 5^th.

3. 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

4. Introductory steps

• Insertion sort
• Analysis of the insertions 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

5. 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
• • Slides illustrating the problems with slolution of nonlinear algebraic equations
• Sequential vs. parallel computing
• • Sequential vs. parallel merge-sort
  • Sequential vs. parallel Strassen Algorithm
  • Sequential vs. parallel recursive algorithms

6. Growth functions

• Θ
• O
• Ω
• o
• ω

7. Solving recurrences

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

8. 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

9. Heapsort

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

10. Quicksort and its flavors

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

11. 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

12. There is a class on Thursday!!! -- Professor Johnson Thomas will talk about data structures and algorithms for networks

Homework 1 (team) (no grade)
Form gropups and submit a short abstract of proposed group project. Due by: Wednesday (August 28^th), before I turn off my computer in the evening

Homework 2 (team)
Create a WWW site for your group project. Due by Thursday, September 5^th at class time. The same grade will be given to all team members.

Homework 3 (team)
Prepare a 10-15 minute presentation summarizing your project. This presentation is to be delivered on Thursday, September 5^th during class time. Presentation will be judged both on its content and form. The same grade will be given to all team members.

Homework 4 (individual)

• 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.
• Part IV In class we have argued that insertion sort can be faster than merge sort when the data is almost sorted. Experimentaly verify this hypothesis. Establish how many unsorted numbers can be added to a sorted squence before merge sort outperforms indsertion sort.

As the final product I want to receive a paper (which in form follows format discussed in class) that summarises the results of your experimental work. Due by Thursday, October 3^rd at class time.

Homework 5 (individual)

• Textbook, page 67, problems 4.1-1 and 4.1-2
• 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, October 24^th at class time.

Homework 6 (individual)

Implement Heapsort; perform experiments comparing its performance with that of the Mergesort. Write a report on your findings. As the final product I want to receive a paper. Due by Thursday, October 31^st e-mailed to me by midnight that day.

Homework 7 (team)

Evaluate WWW-project-sites of the remaining groups. For each group write an evaluation and give a grade form the range 1-10. You will be graded on the evaluation Due by: Thursday, October 31^st. Homework has to be e-mailed to me by midnight (Tulsa time) of that day.

Homework 8 (individual)

Implement Quicksort; perform experiments comparing its performance depending on the pivot selection strategy (utilize all four approaches to pivot selection discussed in class). Write a report on your findings. As the final product I want to receive a paper. Due by Thursday, November 7^th at class time.

Homework 9 (individual)

It has been claimed that the performance of Quicksort can be substantially improved if in the final stages of the algoruthm the recursion is replaced by inserion sort. Experimentally verify this hypothesis. Use the best pivoting strategy established in the previous homework. Due by midnight (Tulsa time), Saturday, November 16^th e-mailed to me.

Reading assignment, textbook pages xiii-164

Back to the syllabus page