Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

COMP 2140 > Test 1 > Flashcards

Test 1 Flashcards

1
Q

What are we considering when we talk about efficiency?

A

The amount of time and storage required to execute the algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How do we measure efficiency?

A

With the help of asymptotic notations

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What does O signify?

A

The maximum running time an algorithm can have, providing an estimation of its worst-case complexity

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Why is O-Notation helpful?

A

It is a measure of run time that
- is independent of a specific machine or implementation
- shows us how the run time scales with the size of the input n
- is algebraically as simple as possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are the key steps for identifying O-notation?

A
  • identify the size of the input (like length of list being sorted, number of entries in a data structure)
  • identify one particular operation, called a basic operation, that is fundamental to the algorithm (comparison of elements in a list, follow a pointer in a traversal)
  • count the number of basic operations that the algorithm performs as a function of n.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the order of common run times?

A

O(1)<=O(logn)<=O(n)<=O(nlogn)<=O(n^k)<=O(k^n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is recursion?

A

The process in which a function calls itself directly or indirectly. A recursive function solves a particular problem by colling a copy of itself and solving smaller subproblems (“smaller” means closer to the base case)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How do proofs by induction work?

A

To prove some statement P(n) is true for all n >=1, prove P(1) then assume P(n-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the main parts of a recursive method?

A

Base case(s): one or more parameter values for which the function does not call itself. The answer is computed directly

Recursive case: the answer to the current problem is calculated from on one or more answers to smaller versions of the problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What happens when a function is called?

A

An activation record is created on the run-time stack. This record contains:
- the parameters received by the function
- the local variables
- the return address to the location in the original routine where this function was called
When the function returns, it is removed from the stack.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How do you calculate run time for recursive functions?

A

In this course, if the function carries out a constant number of operations other than the recursive call, then you can estimate the run time by counting the function calls.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the height of a binary tree?

A

O(log(n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are advantages/disadvantages of recursion?

A

Advantages:
- clean and simple
- MIGHT improve the time complexity
Disadvantages:
- generally requires more space
- generally takes more time to run
- repeated function calls introduce more overhead
- can unnecessarily duplicate work (fibonacci, exponent examples)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When should we use recursion?

A
  • if the recursive method performs redundant calculations, switch to iterative
  • if the recursive method is no simpler than the iterative method, switch to iterative
  • only use recursion on naturally recursive problems, where the recursive solution is the easiest to implement and understand
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are some applications of recursion?

A
  • tree and graph traversal
  • sorting algorithms
  • divide-and-conquer algorithms
  • backtracking algorithms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a divide and conquer algorithm?

A

A strategy for solving a large problem by breaking the problem into smaller sub-problems
1. dividing the problem into smaller, more manageable sub-problems
2. solving these sub-problems individually
3. combining their solutions to obtain the desired overall result

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are some properties to consider when comparing different algorithms?

A
  • correctness
  • time required
  • memory space required
  • simplicity/clarity/maintainability
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are some factors that affect the amount of time it takes to run a program?

A
  1. the conditions of the computer
  2. the choice of programming language, complier,
  3. the quality and accuracy of the implementation
  4. the size of the input
  5. whether the data is convenient (like key for a search being the first thing considered)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the process of the insertion sort?

A

Divides the array into two parts: a sorted section and an unsorted section. Elements from the unsorted part are selected and placed in the correct order within the sorted section

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is the time and space complexity of the insertion sort?

A

Iterative best case:
Time: O(n)
Spacce: O(1)
Iterative worst case:
Time: O(n^2)
Space: O(1)
Recursive:
Time: O(n^2)
Space: O(n) (stack frames!!)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

How do you do an insertion sort using recursion?

A

Base case: if the array size is 1 or smaller, return
Recursively sort first n-1 elements
Insert the last element at its correct position in the sorted array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are advantages and disadvantages of insertion sort?

A

Advantages:
- simple implementation
- efficient for small data values
- appropriate for data sets that are already partially sorted
Disadvantages:
- with a time complexity of O(n^2), it is not efficient for big data sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the process of the selection sort?

A
  1. select the smallest element from the unsorted portion of the list
  2. move it to the sorted portion of the list
  3. repeat until the sorted portion is empty
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the time and space complexity of selection sort?

A

Best case and worst case:
Time: O(n^2)
Space: O(1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is the process for the merge sort?

A
  1. Divide: split the unsorted array into two equal halves until you reach arrays with one element
  2. Conquer: start from the bottom of the tree and combine (merge) each pair of unsorted arrays
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

How do merging algorithms work?

A

Have a pointer to the current element for both subarrays. Compare these elements and place the lesser one in the combined array. Once either pointer is outside the subarray, copy the remaining elements of the other into the combined array.

27
Q

What is the time and space complexity of the merge sort?

A

Time: O(nlog(n)) (there are log(n) rows in the recursion tree, and the merge algorithm requires O(n) time to merge two sorted subarrays whose total length is n)
Space: O(n) (need to create a target for the merging)

28
Q

What are some advantages and disadvantages of merge sort

A

Advantages:
- performs well on large data sets
- naturally parallelizable. Easily parallelized to take advantage of multiple processors.
Disadvantage:
- requires additional memory during the sorting process

29
Q

What is the process of the quick sort?

A
  1. select the pivot element
  2. rearrange the array: elements smaller than the pivot go to the left of the pivot, and elements greater go to the right of the pivot. Finally, add the pivot into the middle
  3. divide subarray and repeat
30
Q

What is the time and space complexity of quick sort?

A

Time: O(nlogn) (worst case O(n^2), but if we pick the pivot well we can avoid this most of the time)
Space: log(n) (worst case n)

31
Q

What is the best method for choosing the pivot?

A

Median of three (find the first, middle, and last elements and take the median of the three as the pivot)

32
Q

When does the worst case for a quick sort occur?

A

When the pivot element is either the greatest or smallest element

33
Q

When does the best case for an insertion sort occur?

A

When the array is already sorted

34
Q

When does the best case for a quick sort occur?

A

When the pivot element is always the middle element (or near the middle)

35
Q

What are some advantages and disadvantages of quick sort?

A

Advantages:
- Efficient on large data sets
Disadvantages:
- not a good choice for small data sets

36
Q

What is the process of counting sort?

A
  • assume all the elements are between a given upper and lower bound
  • count how many times each possible element appears in the array
  • use the counting array to make the sorted array
37
Q

What is the time and space complexity of counting sort?

A

Time: counting every element takes O(n), and translating the counting array to the sorted array takes O(k), where k is the length of the counting array. Therefore the time complexity of O(n+k)

38
Q

When is it a good idea to use the counting sort?

A

When we know that the range of numbers is not much bigger than the number of elements (rule of thumb: k < n^2)

39
Q

What is the process of Radix sort?

A

Find the biggest element (takes O(n)) to declare the number of digits. While i<=d, compare the ith digits of all elements and update the previous unsorted array

40
Q

What does radix?

A

The radix is the number of distinct digits used to represent a number in a place value system

41
Q

What is the time complexity of Radix sort?

A

Let d be the number of digits in the largest element. For each significant digit, do a counting sort that takes O(n+k) (in this case k = 10). Thus the time complexity is O(dn)

42
Q

What are abstract data types?

A

An ADT consists of the following:
- a data structure: a collection of data together with structure, organization, and properties of that data
- the operations that can be performed: what the user can do to look at, manipulate, or change the data
Note: an ADT is distinct from its implementation. (stacks can be implemented using arrays and linked lists)

43
Q

What is the interface between the ADT and the user?

A

The operations that the user is able to perform. Provides a contract between the ADT and the user. The ADT supplies a set of operations and guarantees what the outcome should be, and the user agrees to only use the operations supplied by the interface. This contract allows the developer to change the implementation details without affecting the user’s code.

44
Q

What is the difference between arrays and linked lists?

A

Arrays store elements in contiguous memory locations. Linked lists are less rigid in their storage structure. Since they are usually not stored in contiguous locations, they need to be stored with additional tags giving a reference to the next element

45
Q

What is a linked list?

A

A linear data structure in which elements are linked using pointers. It forms a series of connected nodes, where each node stores the data and address of the next node.

46
Q

What is the node structure?

A

Made up of data (holds the actual value or data associated with the node) and link (stores the memory address of the next node)

47
Q

What are the advantages and disadvantages of linked lists?

A

Advantages:
- dynamic size
- efficient insertion and deletion
- memory efficiency (use more memory, but use the space more efficiently)
- easy implementation of abstract data types like stacks, queues and trees
- more efficient sorting (no swapping required!)
Disadvantages:
- extra memory usage (each element requires space for data AND link) (2 for each data and 2 for the top and bottom pointers, so linear which isn’t too bad)
- No random access
- More complex implementation (requires managing pointers and dynamically allocating memory)

48
Q

What is a singly linked list?

A

Simplest linked list. Each node consists of data and a link to the next node

49
Q

What is the process of a singly linked list search?

A

Unsorted: Start from the top node, and then traverse the nodes until we find the desired value
sorted: iterate until the search key is found or the current is larger than the key

50
Q

What is the process of deletion with singly linked lists?

A
  1. find the node previous to the one being deleted
  2. change the link of the previous node
    If the list is sorted, can check to terminate sooner
    Consider edge cases: no next node, no previous node, no node with the key
51
Q

What are the different categories of linked lists?

A

Ordered versus unordered, linear versus circular, with dummy nodes versus without dummy nodes

52
Q

How do you make a copy of a linked list?

A

Remember that in Java, the simple way of “copying” makes a shallow copy. To make a deep copy, create a new empty list and add entries from the original one by one

53
Q

What is a doubly linked list?

A

A special type of linked list in which each node contains a pointer to the previous node as well as the next node

54
Q

What is a dummy node?

A

A node that marks the start or end of the linked list, but does not contain real data. We call a dummy node at the beginning a header, and a dummy node at the end a trailer. The header and trailer are created by the constructor.

55
Q

What are some ways that linked lists with dummy nodes are different?

A
  • top is never null because it always points to the header
  • any real node has a node preceding it
  • for any real node, link is not null
  • so we no longer need to check for null!
56
Q

How do we distinguish dummy nodes?

A
  • when the data is represented by an object, use null
  • for a sorted list, use extreme values. Integer.MAX_VALUE ajnd Integer.MIN_VALUE, or -1 and 1e8
57
Q

What is the process for searching in a circular linked list?

A

Use a do-while loop, check if we’ve found the data or if we’ve returned to the top

58
Q

What is the process for inserting in a circular linked list?

A

If we want to insert at the beginning, we can have problems updating the link for the last element. Keeping a pointer for the end of the list could make this easier (unless we have a dummy node!)

59
Q

What is the process for ordered insert in a doubly linked list?

A

keep track of curr and previous, have to update next and back of new, if curr is not null update back, if previous is not null update next

60
Q

What is the process for an insertion sort using doubly linked lists?

A
  1. create a new empty list
  2. for each node in the original, do an ordered insert into the new list
  3. change the top of the original to the top of empty
61
Q

What are some applications of doubly linked lists?

A
  • used by web browsers for navigation of web pages (back and forward)
  • Least Recently Used / Most Recently Used cache are constructed using doubly linked lists
  • undo and redo functionalities
62
Q

What are some advantages and disadvantages of doubly linked lists?

A

Advantages:
- can be traversed both forward and backward
- delete is more efficient if a pointer to the node to be deleted is given
- we can quickly insert a new node before a given node
Disadvantages:
- every node of DLL requires extra space
- all operations require an extra pointer back to be maintained (insertion is more complicated)

63
Q

What is a circular linked list?

A

A linked list where all nodes are connected to form a circle. The first node and the last node are connected to each other.

COMP 2140 (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions