[SOLVED] CS SCI 2201/7201 Algorithm & Data Structure Analysis

School of Computer Science
COMP SCI 2201/7201 Algorithm & Data Structure Analysis
Lecture 1 Course Profile and Assessment Information

Copyright By Assignmentchef assignmentchef

Course Outline
Week 1-6: Integer arithmetic, (Matrix) multiplications, Complexity proofs, Trees, Linear time sorting, order statistics
Week 7-12: Hashing, Graph algorithms, Turing machines, Halting problem, Complexity class, NP- completeness

Assessment

Assessment
This course has 2 components: Writtenexamination60%
Practicalassignments40%
You are expected to participate in all activities, attend lectures and submit your assignments on time.
Hurdle: You need at least 40% of the mark of the written examination to pass this course.

If you see an RP on your transcript, it means that your mark is not currently available. If you dont know why, you should contact your course coordinator.

Minimum Performance
On each component with a hurdle, you are required to achieve at least 40% of the marks allocated in the component.
If your mark for any component with a hurdle is less than 40% of the allocated marks for that component, and your overall mark is greater than 45 F, your overall mark will be reduced to 45 F.
To pass the course, you must obtain a passing mark overall and achieve at least 40% of the available marks in components with a hurdle.

Late submission policy
You should hand your coursework in on time.
If you hand in your work late, your mark will be capped, based on how many days late it is.
up to 1 day late mark reduced to 75%, marks below 75% not affected.
up to 2 days late mark reduced to 50%, marks below 50% not affected.
up to 3 days late mark reduced to 25%, marks below 25% not affected.
More than 3 days late mark is reduced to 0.
If you handed in something on time, and it is worth more than something that you handed in late, you will get the higher mark.
Hand in early!

Repeating Students
Students who repeat a course are expected to attempt all of the aspects of the course again. This includes making fresh attempts at all coursework assessment items.
You may apply to the course coordinator to have your previous work counted but this is not usually granted.
Make sure that you attend all of the lectures, do all of the work and study hard for the exam you dont want to get stuck repeating the same course over and over.

Modified arrangements

Assignment extensions
Extensions will not be granted for circumstances including minor ailments; travel, employment, family, customary, sport or leisure commitments; problems with balancing workloads; normal exam stress or anxiety.
If you think your situation is exceptional, contact your course coordinator ASAP, who will then consult the Head of School.
Students who deliberately submit false or fraudulent documentation may be referred to the Student Misconduct Tribunal.
You will normally only receive an extension equivalent to
the number of days covered by your documentation.
Dont expect to get an extra week because you lost a day.

Replacement exams
Replacement exams will not be granted for circumstances including minor ailments; travel, employment, family, customary, sport or leisure commitments; problems with balancing workloads; normal exam stress or anxiety.
Students granted a replacement exam are not eligible to sit the primary exam.
Students who sit the primary exam will not be eligible to apply for a replacement exam unless a major issue arose during the exam.
Students must make themselves available during the replacement exam period.

Replacement exams (cont.)
Students will not be entitled to an additional assessment if they have already sat a replacement exam, i.e., no supps on supps.
Students granted a deferred replacement exam will not be eligible to sit the primary exam or the replacement exam (only under exceptional circumstances will a deferred replacement exam be granted).
The University must notify students of the outcome of their replacement exam applications within 3 business days (if you already sat the primary exam, do not bother applying for a replacement exam).

Replacement exams (cont.)
Students who deliberately submit false or fraudulent documentation may be referred to the Student Misconduct Tribunal.
For the full policy on Modified Arrangements, see: https://www.adelaide.edu.au/policies/3303

Additional/Replacement exam dates
Go to the University Examinations Site for information on Additional/Replacement exams:
http://www.adelaide.edu.au/student/exams/

Academic honesty policies

Academic Honesty Policies
The University has strict policies prohibiting students from presenting other peoples work as their own, whether that of students or from outside the University.
You may not copy code from another student or give another student your code to copy from, unless specifically authorised to do so by a staff member.
You may not copy code from anywhere else, without permission.
If caught, you may receive zero for the assignment, zero for the
course or be expelled.
We dont give you assignment work just to keep you busy, we do it to develop your understanding and ability to apply important techniques.
If you dont do the work yourself, you wont be able to do it in the examination and you wont be able to do it in the work force.
Full policy available at the university webpages.

Violations to policy
Plagiarism
Usinganotherpersonsideas,designs,wordsorworkswithout
appropriate acknowledgment. Collusion
Anotherpersonassistingintheproductionofanassessment submission without the express requirement, or consent, or knowledge of the assessor.

Violations to policy
Plagiarism
Usinganotherpersonsideas,designs,wordsorworkswithout
appropriate acknowledgment. Collusion
Anotherpersonassistingintheproductionofanassessment submission without the express requirement, or consent, or knowledge of the assessor.
1. Do not submit any work or part thereof which is not yours.
2. Do not submit any work for which you have received unfair assistance.

I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
Gavetheclassmateacopyofmycode(orpartthereof).

I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
Gavetheclassmateacopyofmycode(orpartthereof).
Postedmysolutiononanonlineforumforhis/herreference.

I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
Gavetheclassmateacopyofmycode(orpartthereof).
Postedmysolutiononanonlineforumforhis/herreference.
Allowedtheclassmatetohavealookatmycodeon paper/screen.

I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
Gavetheclassmateacopyofmycode(orpartthereof).
Postedmysolutiononanonlineforumforhis/herreference.
Allowedtheclassmatetohavealookatmycodeon paper/screen.

I had finished my assignment, and a classmate was asking for help. Since I am a kind person, I
Gaveafewhigh-leveltipstomyclassmate.
Discussedhigh-levelconceptsregardingtheassignmentwithmy classmate.

My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
Exchangedsolutionstoverify/compareouranswers.

My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
Exchangedsolutionstoverify/compareouranswers.
Dividedtheassignmentworkamongstourselvestospeedup progress.

My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
Exchangedsolutionstoverify/compareouranswers.
Dividedtheassignmentworkamongstourselvestospeedup
Satside-by-sideandlookedateachothersanswerswhendoing the assignment.

My good friend/housemate/brother/twin and I are taking the same course. We have always worked together. When doing the assignment, we
Exchangedsolutionstoverify/compareouranswers.
Dividedtheassignmentworkamongstourselvestospeedup
Satside-by-sideandlookedateachothersanswerswhendoing the assignment.

The assignment seems to be the same as the one given last year. I contacted my friend who took the course last year and got a copy of his solution.

The assignment seemed to be similar to another given at a different university. So, I
Copiedandsubmittedthemodelanswersavailableatthat universitys website.
Tookpartsofthemodelanswersandintegratedthemintomy solution.

I studied at a school/college/university where doing ______________ is acceptable. So I assumed doing this at The University of Adelaide is also acceptable.

How to avoid plagiarism/collusion
If you get stuck, seek help from the lecturer, tutor or prac demonstrator rather than copying from someone else.
Starting your work early will help you to avoid getting stuck at the last minute.
When in doubt, ask your lecturer.

Submission practicals / practical examinations

How to Submit your Practicals
Go to https://cs.adelaide.edu.au/services/websubmission/
There, find the directory name that you need to make in your
svn repository for each assignment
Use secure shell to have external access to universitys computing resources:
ssh uss.cs.adelaide.edu.au
Use svn commands to make the directory
Upload (or make) your files in your directory
Make sure your files are compiled with universitys compiler
Go back to https://cs.adelaide.edu.au/services/websubmission/ and submit your work. (Dont forget this!) and check feedback
Get help from
Your practical/workshop supervisors
https://cs.adelaide.edu.au/current-students/handbook/external/

You know what exactly the repository address of your assignment needs to be (from web-submission)
Use svn commands to make that folder
svn mkdir parents https://version-control.adelaide.edu.au/svn
/aXXXXXXX/what/ever/you/want -m must have some comments
Either from your own terminal
Or from the server, which you connect to by ssh. If you have windows, use Putty (a free ssh client) to connect to the server through ssh
If you dont have a working copy, check out this folder (or one of the parents) to get a fresh working copy of that
svn co https://version-control.adelaide.edu.au/svn /aXXXXXXX/what/ever/you/want localFolderAddress
Either on your own computer
Orontheserver(firstusesshtoconnect)

If you already have a working copy of one of the parent folders,
Eithermaketheassignmentfolder(s)locallyandaddthemby svn commands
cd ExistingParentFolder
svn add NewFolderName
svn ci m comments
Orusesvncommandstomakethatfolder(s)ontheserver
Then update your working copy folder. You will see the new directory in that
cdExistingParentFolder svn update
Try not to have more than one working copy.

Code on the server
If your working copy is on the server
sshtoservereachtimeyouwanttoworkonit
Gotoyourworkingcopyfolder
Usevim(oranyotherterminal-basedtexteditor):
vim main.cpp
g++-Wallmain.cpp

Lets get started

Algorithm and Data Structure Analysis
Lecture 1: Introduction

Motivation
Why is this course important?
Efficient data structures and algorithms are essential for successful computer applications
We need efficient methods on how to store, manipulate data
We need efficient algorithms to search them.
Problems in computer science require efficient
algorithms.
Topic of this course:
Basic data structures and algorithms with focus on their analysis
Algorithm and Data Structure Analysis

Goals We want to have:
Data structures that allow us to carry out operations as efficiently as possible
Algorithms that solve problems as efficiently as possible.
Algorithm and Data Structure Analysis

Appetizer Sorting: Why should I care?
Which one do you prefer?
Algorithm and Data Structure Analysis

Efficiency
Whats our measure?
Let n be the number of input elements (think of number of books)
Measure time for operations on data structures and time to execute algorithms in dependence of n
Consider orders of magnitude Algorithm and Data Structure Analysis

(Almost) Linear Runtime
Algorithm and Data Structure Analysis

Quadratic Runtime
Algorithm and Data Structure Analysis

Cubic Runtime
Algorithm and Data Structure Analysis

Exponential Runtime
Algorithm and Data Structure Analysis

Complexity
1.000.000.000
100.000.000
Its great to have algorithms that run in linear time or time n logn.
Many important problems have algorithms whose runtime is bounded by a small polynomial (e. g. n2 or n3)
For a wide class of important problems there is most probably no algorithm that runs in polynomial time.
Algorithm and Data Structure Analysis

Asymptotic Behaviour
Analysis of the growth rate of a function
We measure runtime as a function of the input size n.
Define complexity depending on the asymptotic behaviour.
Want to have algorithms that solve a given problem and have low complexity.
Algorithm and Data Structure Analysis

Asymptotic Behavior
Algorithm and Data Structure Analysis

Algorithm and Data Structure Analysis

Landau Symbols
We want to measure computation times asymptotically
Mehlhorn, Sanders (page 21)
Algorithm and Data Structure Analysis

Right or Wrong
Right Right
Wrong Wrong
Algorithm and Data Structure Analysis

Efficient data structures and algorithms are
crucial for successful computer applications. Measure runtime as a function of the given
input size.
Asymptotic behavior and complexity classes. Reading: Mehlhorn & Sanders ch 2.1
Algorithm and Data Structure Analysis

Algorithm and Data Structure
Lecture 2: Integer Arithme;cs (Book Chapter 1)

Overview School Method of Addi;on
School Method of Mul;plica;on
Algorithm and Data Structure Analysis

What is an algorithm?
An algorithm is a step by step list of direc;ons
that need to be followed to solve a problem.
Algorithms are oJen used to describe how a
computer might solve a problem.
A recipe can be a type of algorithm. It tells what ingredients are needed to make the dish and what steps to follow. If the recipe tells exactly what to do without too much confusion, then it is an algorithm.
From Wikipedia
Algorithm and Data Structure Analysis

Integer Arithme;cs
We want to have algorithms to carry out
Addi;on
Mul;plica;on of two numbers.
Recall what you have learned in school!
Algorithm and Data Structure Analysis

Example for Addi;on
a = 1289, b = 1342, B = 10
a 1289 b+ 1342
00110 02631
Algorithm and Data Structure Analysis

teach you one of them.
Representa;on
rithmetic on long integers is needed in areas such puting, and computer algebra and so an improved m
Want to inves;gate integer arithme;cs
an intellectual gem but also useful for applications.
Assume that integers are represented as digit analysis and basic algorithm engineering techniq
also see the interplay of theory and experiment.
Base B number system, B>1
e assume that integers are represented as digit str
Digits 0, 1, , B-1
m, where B is an integer larger than one, there ar
string an1an2 a1a0 represents the number represents
0i ms with a small value of B are bPase 2, with digits 0
and base 16, with digits 0 to 15 (frequently written
Store in an array a of size n i=0 i acrognetarinbinagsnedsig,itsu. ch as 28, 216, 232, and 264, are also u
Algorithm and Data Structure Analysis
just basic shall
digit syste to 9, F). L
as c ultip
ings e dig
as 0 seful
10101 in base 2 represents
1 24 +0 23 +1 22 +0

digit string a a a a represents the num shall also see the interplay of theory and experime
h The Soviet stamp on this page shows Muhammad ib
systems with a small value of B are base 2, with We assume that integers are represented as d
entl e, th
to 9, and base 16, with digits 0 to 15 (frequ system, where B is an integer larger than on
8 16 32 dFig)i.tLstarrignegrabaseas, su.c.h.asa2 r,e2pre,se2nts, tahnedn2u
n1 n2 1 0
systems with a small value of B are base 2, wi
10101 inbarseepr2esrenptrsesents 124+
to 9, and base 16, with digits 0 to 15 (frequent
F). 4Larger b3ases, suc2h as 28,1216, 232,0and 264, 924 in base 10 represents
12 +02 +12 +02 +12 =21
10101 inbase2represents 124+0 B=10
We assume that we have two primitive of three digits with a two-digit result (this i
represents
924 in base 10 represents
The Soviet stamp on this page shows Muha
of three digits with a two-digit result (this is s
9102 +2101 +4100 = 924
We assume that we have two primitive o
mately 780; died between 835 and 850), Per
Khorasan province of present-day Uzbekista
Algorithm and Data Structure Analysis

Primi;ve Opera;ons Assume that we have access to
Addi;on of 3 digits with a 2 digits result (full adder)
1 Appetizer: Integer Arithmetics
Mul;plica;on of 2 digits with 2 digits result
2 1 Appetizer: Integer Arithmetics 2 plication of two digits with a two-digit result. For exa
multiplication of two digits with a two-digit result.2 For example, in bas
Example (B=10): 3
Mul;plica;on
6 7 = 42 . 6 7 = 42 .
5 Addi;on 5
We shall measure the efficiency of our algorithms by the number of primitiv alltimonesaexseucruetedth. e efficiency of our algorithms by the numbe
Algorithm and Data Structure Analysis
We can artificially turn any -digit integer into an -digit integer for any
multi have
mple, e 10, w
e oper r of
nmmnb adding additional leading zeros. Concretely, 425 and 000425 represent the sam
tions executed.
y We can artificially turn any n-digit integer into an m-digit integer fo

Example for Addi;on
a = 1289, b = 1342, B = 10
a 1289 b+ 1342
00110 02631
Algorithm and Data Structure Analysis

denote the digits of b, and write b = (bn1 b0). 1.1
We We sim um the git is c ly,
School Method for Addi;on
all know how to add two integers a=(a a ) and b=(b b ). Input: Two integers a = (a n1a ) a0nd b = (b n1b0 )
an1 a1 a0
bn1 b1 b0 cn cn1 c1 0 sn sn1 s1 s0
first operand second operand carries sum
n1 0 n1 0
ply write one under the other with the least significant digits aligned, and s
Compute: s = a + b,
integers digitwise, carrying a single digit from one position to the next. This di
wheres=(s s )isann+1digitinteger.
alled a carry. The resnult will b0e an n + 1-digit integer s = (sn . . . s0 ). Graphical
erec toc isthesequenceofcarriesands=(s s )isthesum.Wehavec = c c is sequence of carries.
nn00 n0 0 1B+si =ai+bi+ci for0i CS : assignmentchef QQ: 1823890830 Email: [email protected]