Information about the timing functions

Material covered:

Part One (Overview of ANSI C) is to be done by the students (as necessary)

Introduction to Recursion

definition of recursion
factorial calculation as example of simple recursion
Fibonacci numbers (pros and cons of recursion)
other examples of recursion


Recursion -- examples

Towers of Hanoi
Generating permutations
Applications of recursion in graphics


Backtracking Algorithms

Maze problem and backtracking
Backtracking and the game of nim
Backtracking and tic-tac-toe
Generalized two-player games
Minmax strategy for the game of nim
Minmax strategies for two-player games


Algorithm complexity analysis (and recursion)

Selection sort and its complexity
Doubling and splitting a quadratic
Big Oh notation
Worst-cse and average-case complexity
Big O definition
Sorting by merging (merge sort)
Complexity of merge sort
Most important cases of complexity
Quicksort


Abstract Data Types

Concept of an ADT
Stack as an example of an ADT
Other possible ADT's and their advantages and disadvantages


Abstract Data Types and Efficiency
Importnace of splitting "interface" and "implementation"
Implementing an "editor"

Array based implemtation
Two-stack based implementation
Linked list based implementation

Symbol tables/Look-up tables

Definition
Array based implementation
Array based sorted implentation
Hashing fuction
Efficiency of hashing

C as a language not ready for ADT's


Recursive data
Recursive lists

Linked lists as recursive objects
Recursive functions for recursive linked lists
Recursive list based implementation of extended arithmetic





Homework 1


Page 190, problem 2
Page 193, problem 9
Due by, Tuesday, September 12th, before class


Homework 2


Page 224, problem 3
Page 225, problem 5
Due by, Tuesday, September 26th, before class


Homework 3


Implement Merge Sort
Implement Quicksort
Send working codes of both sorts to me
Learn how to measure a time of an algorithm execution -- see the link above
Learn how to use a random number generator
Due by, Tuesday, October 3rd, before class


Homework 4


Write a paper comparing the performance of Quicksort and Merge Sort.
Due by, Tuesday, October 24th, before class


Homework 5


Implement a stack using a linked list and using an array.
Implement a queue using a linked list and using an array.
Due by, Tuesday, Noveber 7th, before class


Reading assignment - pages 1-536