COURSE DESCRIPTION

COURSE DESCRIPTION

Department and Course Number: CSE 3353

Course Instructor: Alexandru Fit-Florea

Summer Class' Schedule: T, TH 5-7; 10 weeks, Summer 3

Course Title: Discrete Mathematics with Algorithms

Total Credits: 3

Catalog Description:

Introduction to algorithm analysis, big Oh notation, classifying algorithms by efficiency. Algorithms for: arithmetic operations, binomial coefficients, prime factorization, gcd. Sorting and selection algorithms. Introduction to graph theory, graph algorithms.

Textbook: Discrete Mathematics with Algorithms, Albertson, M. O., and Hutchinson, J.P., Wiley 1988

Course Goals:

This course presents the fundamentals of algorithm design and analysis. Algorithm case studies are employed to identify design principles and illustrate analyses of algorithm efficiency relevant to software and hardware design. Algorithms from arithmetic and number theory are developed with reference to computer hardware design. Algorithms for selection, sorting, and graph theory are developed with applicability to efficient software design. The intent is to jointly develop familiarity with terminology, elementary theory, and efficient algorithms in the areas of arithmetic, sorting, and graph optimization problems.

Prerequisites by Topic: CSE 2353. [Particular topics required: number, vector and matrix representation; fundamentals of set theory; elementary combinatorics; proof techniques.]

Major Topics Covered in the Course:

1) Introduction to Algorithm Analysis 2 classes

2) Arithmetic algorithms 9 classes

3) Sorting and selection algorithms 7 classes

4) Graph theory 5 classes

5) Graph and network algorithms 5 classes

6) Exams 2 classes

CSE 3353 Discrete Mathematics with Algorithms

Text: Discrete Mathematics with Algorithms, Albertson, M. O. and Hutchinson, J. P., Wiley 1988

Note: Chapters 2, 4, 5, 6 and 8 are substantially independent of the coverage of CSE 2353, and form the foundation of the course. Chapters 1 and 3 cover elementary number systems, set theory and combinatorics, and will be cited for reference review of CSE 2353 material without lecture coverage.

Topics to be covered (emphasis on algorithmic fundamentals):

Algorithms in Arithmetic and Number Theory

Using the number of integer addition, multiplication and division operations as an efficiencey measure, algorithms are given and analyzed for: exponentiation, logarithms, binomial coefficients, prime factorization, gcd, and multiplicative inverses module a prime. Big Oh notation is introduced and employed to describe the time and space efficiency of algorithms (i.e. their algorithmic complexity). Moving from integer operations to the digit level, the traditional algorithms for long multiplication, long division, and digitwise addition are analyzed at the decimal digit and binary bit operation count level, with applications to hardware unit design noted.

Text: Chapter 2 – Arithmetic, Chapter 4 - Number Theory

Algorithms for Selection and Sorting

This topic starts with sequential and binary search strategies, and then presents and analyzes the following sorting algorithms:

SELECT-, INSERTION-, BUBBLE-, TREE-, MERGE-, and BUCKET-SORT. Comparison trees are introduced and used to verify optimality of small searches and of the n log n sorting lower bound. Sorting algorithms are analyzed for time efficiency, space utilization, and ease of program implementation.

Text: Chapter 6 - Searching and Sorting

Graphs and Networks: Theory and Algorithms

Fundamental graph theoretic concepts covered include graph representation, isomorphism, paths and distance, connectivity, spanning trees, cycles and tours, complete subgraphs and coloring. Algorithms presented include:

Breadth first and depth first search, isomorphic trees, minimum weight spanning tree, minimum distance tree, Euler tour, approximate traveling salesperson tour, and various versions of sequential coloring.

Text: Chapter 5 - Graph Theory, Chapter 8 - More Graph Theory

Topic I Algorithms in Arithmetic and Number Theory 6 weeks 9 lectures 2 homework reviews 1 exam Chapter 2: Arithmetic Chapter 4: Number Theory	Lecture 1: Problems and algorithms. Example algorithms: arithmetic - decimal to binary conversion; enumeration - smallest prime factor; selection-determine maximum element; graphs - determine graph components from graph matrix. Discuss course prerequisites in: set theory, vector and matrix representation, elementary combinatorics [Chapters 1, 3].
	Lecture 2: Determining problem size and algorithm efficiency. Counting digit length for size and arithmetic operations for efficiency of arithmetic algorithms. Counting comparisons for selection and sorting efficiency. Counting graph matrix references for graph algorithm efficiency. Application to algorithms of Lecture 1.
	Lecture 3: Exponentiation algorithms, floor, celing, base 2 logarithms, base 2 logarithm algorithm [2.1, 2.2, 2.5]
	Lecture 4: Primes, enumerating primes, sieve of Eratosthenes, unique prime factorization, extended Eratosthenes algorithm for smalles prime factor enumeration, prime factorization algorithm.
	Lecture 5: Recognizing good and bad algorithms, growth rate classification: linear, polynomial, logarithmic, exponential; big Oh function bounds [2.6, 2.7, 2.8, 2.10]
	Lecture 6: Counting subsets and combinations with binomial coefficients, Pascal’s triangle for enumerating (), estimating (), multiplicative () evaluation and overflow, additive () evaluation algorithm, space complexity of () algorithms. [3.2, 3.3, 3.6]
	Lecture 7: Estimating n^throot of n!, Stirling’s formula. Comparing exponential growth rates: 2ⁿ, 2 ^{n log n} and . n! prime factorization algorithm, using () prime factorization to estimate the count of primes. [3.4, 3.5]
	Lecture 8: Greatest common divisor (GCD), subtractive GCD algorithm, Euclidian algorithm, Fibonacci numbers, normalized binary integer addition/subtraction, binary GCD algorithms, complexity of GCD algorithms. [4.1, 4.2, 4.3, 4.4, 4.5]
	Lecture 9: Digit level algorithms for arithmetic operations. Long multiplication algorithm in decimal and binary. Long division in decimal and binary. Carry ripple and carry saving digitwise addition algorithms in binary. Digit level efficiency of arithmetic operation algorithms. Relations to hardware arithmetic unit design.
Midterm Exam 1 End of 6^th Week	Exam coverage: Fundamental algorithm design and analysis techniques, arithmetic algorithms.

Topic II Selection And Sorting: [Theory and Algorithms] 4 weeks 6 lectures 1 homework review 1 exam Chapter 6: Searching and Sorting	Lecture 1: Searching, sequential search, max, min, sorting, SELECTSORT, binary search. [6.1, 6.2]
	Lecture 2: INSERTIONSORT, BUBBLESORT, sorting algorithm efficiencies in time and space, sorting nearly sorted lists. [6.3]
	Lecture 3: TREESORT (tournament sort), O(n log n) time sorting, median, k th largest. [6.4]
	Lecture 4: Comparison trees, lower bounds on: (i) max, (ii) max and min, (iii) selection, (iv) sorting [6.5]
	Lecture 5: Recursion, MERGESORT, Divide-and-Conquer algorithm paradigm, BUCKETSORT, radix sort, comparison based sorting vs. indexed buckets [6.6, 6.7]
	Lecture 6: Comparison trees for optimal sorts and selections in small sets, median of five, 4^th of 8, sorting, 4, 5 and 6 elements.
Midterm Exam 2 – End of 10^th Week	Exam Coverage: Emphasis on topic II (plus combinatorics background).
Topic III Graphs and Networks: [Theory and Algorithms] 5 weeks 8 lectures 1 homework review 1 exam review Chapter 5. Graph Theory Chapter 8. More Graph Theory	Lecture 1: Graphs, vertices, edges, adjacency, incidence, degree, graph diagrams, graph representation [5.1, 5.2]
	Lecture 2: Complete graphs, bipartite graphs, adjacency matrix, vertex labeling, graph drawing, isomorphic graphs [5.2]
	Lecture 3: Paths, cycles, components, trees, isomorphic trees, tree isomorphism algorithm [5.3]
	Lecture 4: Spanning trees, breadth first search, shortest path algorithm, distance matrix, weighted graphs, networks, minimum weight spanning tree problem [5.3]
	Lecture 5: Minimum weight spanning tree algorithms, minimum distance problem, minimum distance spanning tree algorithm, Greedy algorithm paradigm [5.4, 5.5, 8.1]
	Lecture 6: Eulerian cycles, Eulerian cycle algorithm, Eulerian paths, Chinese postman problem, matching problem [8.2]
	Lecture 7: Hamiltonian cycles, Hamiltonian graphs, depth first search, traveling salesperson problem, approximation algorithm for traveling salesperson problem [8.3, 8.4]
	Lecture 8: Graph coloring, chromatic number bounds, sequential coloring algorithms, planar graphs, Euler polyhedron formula.[8.5]