**CSci**** 242. Algorithms and Data Structures**

**Term: **Fall 2017.

**Class Hours:** 11:00 - 12:15
PM, T/R

**Room:** 106
Streibel

**Instructor:** Dr. M. Eunjin Kim

**E-mail:** ejkim@cs.und.edu;

**Office: **215 Streibel

**Phone:** (701)777-3338

**Office Hours:** 1:00 - 3:30 PM Wed.

**TA: **TBD (RM. 219) (who@und.edu)

**TA's Office Hour: **? - ?? PM, TBD. (Rm. 219)

**Recitation Class: **6:00 PM, TBD. (Rm. 238)

**Prerequisites:**

Csci 161
Computer Science II: Java

Math 208: Discrete Mathematics

**Required Textbook:**

*Algorithm Design and
Applications*

Michael T. Goodrich, Roberto Tamassia

Wiley, October 2014.

**Recommended Book: **

** Intro Introduction to
Algorithms, 3rd ed**.

Thomas H. Cormen
et.al.

The MIT Press, 2009.

*Data Structures and
Algorithms in Java 6/e*

Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

Wiley, January 2014.

**Course Webpage:**

https://blackboard.und.edu/index.asp.

**Grade Policy**:

Midterm: Part I & II - 25
(or 20)%

Final Exam: Part III & IV
(& VI). - 25
(or 20)%

Assignments & Quizzes: 25
(or 20)%

Project: 25 (or 20)%

Attendance:
5%

**Final Grade Policy:**

Midterm = ** y_{1}**; Your Midterm Score =

Final Exam = ** y_{2}**; Your Final Exam Score =

HW/Q Total = ** y_{3}**: Your Total HW Score =

Project = ** y_{4}**; Your Project Score =

Attendance = ** y_{5}**. Your Attendance =

Your Total of Final Grade **=
x_{1}**

A: 900 - 1000

B: 800 - 899

C: 700 - 799

D: 600 - 699

F: 0 - 599

**FINAL EXAM:**

1:000 PM, December 14^{th }(Thr.) ^{}2017.

**COURSE
DESCRIPTION**:

The data structures and
algorithms are the basic elements for problem solving and further build the large
and complex software artifacts. This course provides the students with the
basic theory/implementation of algorithms, the fundamental data structures,
algorithm design techniques, and the analysis of algorithms. The topics
include: data structures, such as trees, priority queue, heap, hash table and
graph; the advanced algorithms such as sorting algorithms and graph algorithms;
the algorithm design techniques such as divide-and-conquer, dynamic programming
and greedy method; and the asymptotic analysis of algorithm in terms of the
order of growth of the function such as upper bound (O), lower bound (W) and tight bound (Q). Thus, the students are expected to have a good
understanding of various data structures, algorithms for problem solving,
algorithm design techniques and its analysis skill enough to design the correct
and efficient algorithms for complex software artifacts.

**ABET Outcome:**

a)
*An ability to apply
knowledge of computing
and mathematics appropriate to the
discipline.*

*i**) An ability to use current techniques, skills, and
tools necessary for computing practice.*

*j) An ability
to apply mathematical foundations, algorithmic principles, and computer science
theory in the modeling and design of computer-based systems in a way that
demonstrates comprehension of the tradeoffs involved in design choices.*

**SELECTED TOPICS:**

0.
Preface

Chap.
1. Algorithms Analysis

I.
Data Structures

Chap.
2. Basic Data Structures

Chap.
3. Binary Search Trees

Chap.
4. Balanced Binary Search Trees

Chap.
5. Priority Queues and Heaps

Chap.
6.Hash Tables

Chap.
7.Union-Find Structures

II.
Sorting and Selection

Chap.
8. Merge-Sort and Quick-Sort

Chap.
9. Fast Sorting and Selection

III. Fundamental Techniques

Chap.
10. The Greedy Method

Chap.
11. Divide-and-Conquer

Chap.
12. Dynamic Programming

Chap.
13. Graphs and Traversals

IV. Graph Algorithms

Chap.
14. Shortest Paths

Chap.
15. Minimum Spanning Trees

VI.
Additional Topics

Chap.
20. B-Trees and External Memory