Transcript Administrivia

RAIK 283
Data Structures and Algorithms
Dr. Ying Lu
[email protected]
Schorr Center 104
472-5793
Aug 28, 2012
http://www.cse.unl.edu/~ylu/raik283
Lecture

Data Structures and Algorithms



TuTh 1:30-3:20pm
Kauffman 112
Instructor: Dr. Ying Lu



Office hours: TuTh 12:20-1:20pm and by
appointment
Office: Schorr Center 104, 472-5793
e-mail: ylu AT cse dot unl dot edu
TAs

David Stephens




Office hours: W 8:00-9:00pm and by
appointment
Office: Kauffman 302
e-mail: davidstephens92 AT gmail dot com
Jordan Degner



Office hours: M 8:00-9:00pm and by
appointment
Office: Kauffman 307A
e-mail: jdegner0129 AT gmail dot com
Textbook

Introduction to the Design and Analysis of
Algorithms (3nd Edition), by Anany Levitin,
Addison Wesley
Course Theme

Data structure


An algorithm


a set of instructions that, when followed, solve a
specific problem
Programs


a way of storing data in a computer so that it can be
retrieved efficiently when required
implementations of algorithms that are executed by
computers
Better algorithms

 huge performance improvement in resultant
programs
Course Objectives




Study classic data structures and algorithms that
solve common problems
Learn standard approaches to solving new
problems
Follow a rigorous approach to analyze and
compare algorithms
When needed, some discrete mathematics will
be covered, since it forms the foundation for
rigorous analysis
Broader Objectives



Learn critical thinking
Learn how to learn (on your own)
These objectives will be met through





interactive classroom discussions
challenging assignments
regular quizzes
progress assessment test (PAT)
final exam
Topics Covered (I)


The basics of algorithm analysis
Algorithmic techniques





Brute Force
Divide-and-Conquer (Decrease-andConquer, and Transform-and-Conquer)
Space and Time Tradeoffs
Dynamic Programming
Greedy Techniques
Topics Covered (II)

Theory of computing





Finite state machines
Halting problem
Tractable and in-tractable problems
Complexity classes, like P, NP & NP-Complete
Advanced topic: linear programming
Prerequisite:
CSCE /RAIK 184H

Mastery of data structures including list,
stack, queue, tree, and graph

Familiarity with recursion

Exposure to complexity analysis
Grading





Class Participation 6%
Assignments 50%
Quizzes 24%
PAT 2%
Final 18%
Letter Grade

No incomplete (I) will be given
A+  97 B+  87 C+  77 D+  67 F < 60
A  93 B  83 C  73 D  63
A-  90 B-  80 C-  70 D-  60
Class Participation





Attend classes
Participate in class discussions
Volunteer to solve in-class problems on
the white board
Do not use laptop, ipad, iphone, or any
device that pull your attention away from
the class!
Check your email regularly, of course
outside of the classroom 
Assignments



Homework will be assigned about every three
weeks
Totally, 4 assignments
Each assignment


includes analytical (pen and paper) problems and
a programming exercise
will be due at the beginning of the class on the
given due date
Late Homework

Late homework is “OK” but...




Only if it’s not too late
You’re not late too often
All homework submitted after its deadline is
considered late
Assignments
 submitted within 24 hours after the original
deadline are considered to be “one day late”,
 within 48 hours, “two days late”, etc.
Late Homework Details

A late homework assignment will be
accepted without penalty if



the total “lateness” of all homework assignments
received to date (including the current
assignment) does not exceed 3 days
The penalty for late assignments is 25% per
day they are late
Weekends count in evaluating the lateness
of an assignment
Quizzes


Quizzes, will be given in-class
approximately every two weeks (MAY NOT
be announced in advance)
Format:

Problems based on the materials covered in
the immediate past
Course Conduct

You may work in groups in




You may not




understanding assignments
developing approaches and strategies
learning to use programming tools
develop joint solutions with other students
share code with other students
copy anything
All assignments, except for the last
programming exercise, constitute a team of
size one!
Announcement

To build our class roster



Send our TA David Stephens
(davidstephens92 AT gmail dot com) an email
with subject “RAIK283 roster”, your photo
(<2MB) and your name by this Thursday
Class roster example
Count toward your class participation
Announcement


Next, we will begin to study chapter1 in
the textbook
Reading List of the Week

Chapter 1, Chapter 2.1, Chapter 2.2