Description

Course Introduction
We will introduce algorithm design and analysis principles.
Welcome!
This course is entitled CSC6013 Algorithms and Discrete Structures.
This course comes just after the
Foundations of Programming course
(CSC6003), and it followed by the
Advanced Algorithms course (CSC6023), which is the continuation of the important topic of Algorithms. This is probably the more important course in the formation of a Computer Scientist.
● Course format
● Timeline
● Evaluation
● Python
CSC 6013 – Week 1

Success Coach and Graduate Advising ● ecs-grad-advising@merrimack.edu
Course Format
Student Tutors available!
Visit the Hub!
Send me an email if you are planning to attend office hours
This course is fully online, all weeks will have:
● Live sessions every Mondays 6:30pm to 8:30pm
● Office Hours every Wednesdays 8:30pm to 9:30pm
Every week, but the last, we will have:
● In-class exercises tasks until Friday
● Quizzes to be taken from Friday to Next Monday
● Coding assignments to be turned in until Next Monday
Email subjects have to start with
CSC6013
Last week has:
● Final exam to be done until Saturday
Communication
● fernandesp@merrimack.edu
Course Format
● Live sessions every Mondays 6:30pm to 8:30pm
○ Meeting ID: 960 3746 8498 Passcode: CSC6013
● Office Hours every Wednesdays 8:30pm to 9:30pm
○ Meeting ID: 960 3746 8498 Passcode: CSC6013
● In-class exercises tasks until Friday
○ Simple exercises, few or no coding
● Quizzes to be taken from Friday to Next Monday
○ Ten multiple choice questions, open book, open notes, and untimed
● Coding Projects to be turned in until next Monday
○ Programming tasks (mostly)
● Final exam to be done until last Saturday of classes
○ 8 questions, 4 hours to take it, open book, open notes
Attendance is optional, but strongly recommended!

The Python language
In the unlikely case you don’t have Python in your machine, do install it now!
● Python Language – A new language after version 3;
○ Any version is fine, but to make things easier, I suggest you to use a version 3.9 or after, since before that there were more significant changes for basic Python commands;
● The default Integrated Development Environment (IDE) that comes with Python is IDLE, a simple and reliable environment;
○ You are free to use other IDE (PyCharm, VScode, etc.), but in this class we will assume everyone is using IDLE, since if a piece of code runs on IDLE it will run in any other environment, but the inverse is not true.
Resource: Python.org.

Basic Data
Structures
To structure data we create an abstraction, a different, usually more restrictive, way to access it.
We structure data in order to better grasp it.
There are implementation choices, but according with the usage we define what can be done or not with a data structure. As such, the definition of what can be done may guide us to choose an implementation.
● Arrays; ● Linked Lists; ● Other Structures.
CSC 6013 – Week 1

addr [0] addr [1] addr [2] addr [3] addr [4]
3 5 6 7 8
Basic Structures – Arrays
x – array address x x+s x+2s x+3s x+4s
Arrays in Python s – size of elements x+0s x+1s x+2s x+3s x+4s
● In Python, depending the version details, arrays are implemented using Python Lists, which may or may not be actually implemented as regular arrays, with an amount of memory equal to:
○ Number of elements times size of each element;
● This amount of memory is indexed by a common arithmetic operation, so data has to be contiguously disposed in the memory;
● We will assume this is the way arrays are implemented in Python, as it serves our theoretical analysis needs.
Wikipedia: Array (data structure).

Basic Data
Structures
To structure data we create an abstraction, a different, usually more restrictive, way to access it.
We structure data in order to better grasp it.
There are implementation choices, but according with the usage we define what can be done or not with a data structure. As such, the definition of what can be done may guide us to choose an implementation.
● Arrays; ● Linked Lists; ● Other Structures.
CSC 6013 – Week 1

Basic Data
Structures
To structure data we create an abstraction, a different, usually more restrictive, way to access it.
We structure data in order to better grasp it.
There are implementation choices, but according with the usage we define what can be done or not with a data structure. As such, the definition of what can be done may guide us to choose an implementation.
● Arrays; ● Linked Lists; ● Other Structures.
CSC 6013 – Week 1

Other Structures – Stacks and Queues
When using specific data structures, as queues and stacks, it may be more interesting to use an array, or a linked list implementation.
Queues:
● a list in which elements can only be inserted by one end, and the elements removed can only be removed by the other end of the list; Stacks:
● a list in which elements can only be inserted and removed by one end of the list.
Lists, in CS, are any form of organized content that can be accessed in an orderly fashion, but not necessarily by a simple indexing procedure.

Other Structures – Stacks and Queues
When needing a queue where access of the elements is frequently needed:
● Maybe arrays is an interesting implementation, because:
○ Arrays are better accessing elements freely;
When needing a queue where no access of the elements is needed:
● Surely linked lists is an interesting implementation, because:
○ Linked Lists are good accessing both ends of the list;
When needing a stack where access of the elements is frequently needed:
● Surely arrays is an interesting implementation, because:
○ Linked Lists are bad accessing elements freely;
When needing a stack where no access of the elements is needed:
● Maybe linked lists is an interesting implementation, because:
○ Arrays and Linked Lists are good accessing only one end of the list.
It depends…
Other Structures – Trees and Graphs
Trees are frequently implemented similarly to linked lists:
● Nodes with data and as many pointers as possible children of each node;
○ check out the lecture on trees from CSC6003.
Graphs are frequently implemented using:
● if using adjacency matrix, double dimension arrays (a matrix);
● if using adjacency list, either and array or linked lists; ○ check out the lecture on graphs from CSC6003.
According to the processing needs, the choice of implementation may play a very large role about the code efficiency.
It is not a bad idea to revise trees and graphs for some algorithms we will see in the next classes.

In-class Exercise – E#1
Use the LinkedList and Node class to manipulate a LinkedList doing the following operations:
● Include in this order the following numbers at the beginning of the list (they will be in reverse order because of it):
○ 76, 88, 11, 34, 56, 91;
● Print out the current status of the list;
● Push the Current to the third element of the list;
● Remove the next to the current element; ● Insert 23 next to the current element of the list; ● Print out the current status of the list.
You have to submit a .pdf file with your main code, plus the output for the executions above.
First Coding Project – P#1
● Create a program that reads a list of Integer numbers from a file named data.txt (create your own file with about 16 numbers – no repetitions and one number per line);
● Store those numbers into an array a and sort it: a.sort();
● Use the LinkedList and Node classes seen in class to store the ordered elements of a into a LinkedList structure L;
● Ask the user an Integer value x;
● Look for the position to insert x in L;
○ If the value x is already in L, remove it;
○ If it is not, insert x in the appropriated position so L remains sorted.
Your task:
First Coding Project – P#1
● This program must be your own, do not use someone else’s code:
○ Make sure you fully understand the examples you use as learning source,
○ do not copy, neither retype seeing the source; ● To additional help:
○ Book a time slot with the student tutors to any help (see “Start Here” module),
○ Any specific questions about it, please bring to the Office hours meeting this Wednesday or contact me by email (put CSC6013 in the subject);
● This may be a challenging program, and it is intended to make sure you are mastering Python data structure manipulation;
● The documentation is not required, but include in your code your name.
● You can (and should) submit a .py file, no need to zip or rename the file extension.
First Quiz – Q#1
● The first quiz in this course covers the topics of Week 1;
● The quiz will be available this Friday, and it is composed by 10 questions;
● The quiz should be taken on Canvas (Module 1), and it is not a timed quiz:
○ You can take as long as you want to answer it (a quiz taken in less than one hour is usually a too short time);
● The quiz is open book, open notes, and you can even use any language Interpreter to answer it;
● Yet, the quiz is evaluated and you are allowed to submit it only once.
Your task: