Discrete Struc 2 Flashcards
What is the general meaning of a graph?
A plot or chart of numerical data using a coordinate system.
What is the technical meaning of a graph?
A discrete structure used to represent relations with a web-like graphical representation.
What are some applications of graphs?
Networking scheduling
What is a simple graph?
A graph that corresponds to symmetric irreflexive binary relations.
What is a multigraph?
A graph that allows multiple edges between two nodes.
What is a pseudograph?
A graph that allows self-loops (edges connecting a node to itself).
What is a directed graph?
A graph where edges have a direction (e.g. one-way streets).
What is a directed multigraph?
A graph that allows multiple directed edges between two nodes.
Give an example of a simple graph.
Vertices: States in the southeastern U.S.; Edges: Pairs of states that are adjacent.
What do simple graphs represent?
Relationships between people such as acquaintanceship and friendship.
What is a multigraph?
A graph that represents networks with multiple lines such as computer networks.
What distinguishes a pseudograph from other graphs?
A graph that represents networks with multiple lines
What do directed graphs represent?
Relationships with direction such as one-way streets.
What is a directed multigraph?
A graph that represents networks with multiple one-way connections like telephone networks.
What is the Handshaking Theorem?
The sum of the degrees of all vertices in a graph is twice the number of edges.
What is the degree of a vertex?
The number of incident edges connected to that vertex.
What is the difference between in-degree and out-degree?
In-degree is the number of edges going to a vertex while out-degree is the number of edges coming from a vertex.
What are adjacent vertices?
Vertices that are connected by an edge.
What is a simple graph?
A graph that has no loops or multiple edges.
What is the degree of a vertex in a graph?
The sum of in-degree and out-degree.
What does the Directed Handshaking Theorem state?
The sum of the in-degrees of all vertices equals the sum of the out-degrees which is equal to the number of edges.
What are some examples of social network graphs?
Acquaintanceship, friendship
What types of graphs are used in communication networks?
Call graphs and message graphs.
What are web graphs and citation graphs examples of?
Information networks.
What do module dependency graphs represent?
Software design applications.
What types of graphs are used in transportation networks?
Airline routes and road networks.
What are round-robin and single-elimination examples of?
Tournaments.
What is an edge list in graph representation?
A list of all edges in the graph.
What does an adjacency matrix represent?
The presence or absence of edges between vertices.
What is an adjacency list?
A list of adjacent vertices for each vertex.
What is the time complexity for edge queries using an edge list?
O(E).
What is the time complexity for neighbor queries using an adjacency matrix?
O(V).
What is the time complexity for edge queries using an adjacency list?
O(degree(v)).
What are pointers in C++?
Variables that store memory addresses of other variables.
What is dynamic memory allocation?
Requesting memory at runtime using the new operator.
How do you deallocate memory in C++?
By using the delete operator.
How do you declare a pointer to an integer in C++?
Using the syntax: typename pointername; e.g. int ptr;
What does the address-of operator (&) do?
Extracts the address of a variable.
What does the dereference operator (*) do?
Accesses the value that a pointer variable points to.
What is the relationship between the & and * operators?
They are inverses of each other; *&x cancels out.
How do you modify the value at a pointer’s address?
By dereferencing the pointer and assigning a new value
What does the new operator do in C++?
Allocates memory on the heap.
What does ‘int *p = new int;’ do in C++?
Allocates memory for a single integer.
How do you allocate memory for an array of 10 integers in C++?
Use ‘int *arr = new int[10];’.
What is one advantage of dynamic memory allocation?
Use ‘int *arr = new int[10];’.
How do you create a dynamic array in C++?
Use ‘int *array = new int[n];’ after getting the size from user input.
What operator is used to free memory allocated for a single variable?
The ‘delete’ operator.
What operator is used to free memory allocated for an array?
The ‘delete[]’ operator.
How do you declare a dynamic 2D array in C++?; Use ‘int **array = new int *[rows];’.
Use ‘int **array = new int *[rows];’.
What additional step is needed after declaring a dynamic 2D array?
Allocate memory for each row using ‘array[i] = new int[cols];’.
How do you access and modify elements in a 2D array in C++?
Use nested for loops to iterate through rows and columns e.g.
What is the purpose of the delete[] operator in C++?
To deallocate memory allocated for an array.
What is a permutation?
An arrangement of items in a specific order where order matters.
How can permutations be calculated using the Fundamental Counting Principle?
By multiplying the number of choices for each position.
What is the factorial notation for permutations of n items?
n! (n factorial).
What is the permutation formula for choosing r items from n?
nPr = n! / (n - r)!
What is a combination?
An arrangement of items where order does not matter.
How can combinations be calculated using the combination formula?
nCr = n! / (r! * (n - r)!) for combinations of n items chosen r at a time.
In the example of arranging the letters ABC how many choices are there for the first blank?
3 choices.
What is the formula for total permutations of n items?
n! (n factorial).
How many total permutations are there for arranging 3 letters from the set ABC.
6 (3!)
How many ways can 5 books be arranged on a shelf?
120 (5!).
How many permutations are there for arranging 3 balls out of 7?
210 (7 * 6 * 5).
How many combinations are there for selecting 3 essay questions out of 5?
10 (5 * 4 * 3 / (3 * 2 * 1)).
How many ways can a basketball starting lineup be selected?
120 (2 * 10 * 6).
What C++ standard library is used to generate permutations?
std::vector and std::algorithm.
What function is used in C++ to generate the next permutation?
std::next_permutation.
What is the method to generate combinations in C++?
Using a specific combination generator code.
What technique is used to generate combinations?
Recursion.
What is the purpose of backtracking in combination generation?
To explore different combinations.
How is the current combination stored during generation?
In a vector.
What are permutations?
Arrangements of items in a specific order where order matters.
What is the formula for permutations?
nPr = n! / (n - r)!
What are combinations?
Arrangements of items where order does not matter.
What is the formula for combinations?
nCr = n! / (r! * (n - r)!)
How many ways can you arrange the letters ABCD using permutations?
12 ways (4P2 = 4! / (4 - 2)!).
How many ways can medals be awarded to 12 athletes?
1320 ways (12P3 = 12! / (12 - 3)!).
How many ways can you fill 5 positions from a club of 24 members?
7920 ways (24P5 = 24! / (24 - 5)!).
How many ways can you form a committee of 3 from 8 people?
56 ways (8C3 = 8! / (3! * (8 - 3)!) ).
What is the formula for permutations?
nPr = n! / (n - r)! where n is the total number of items and r is the number of items to be arranged.
What is the formula for combinations?
nCr = n! / (r! * (n - r)!) where n is the total number of items and r is the number of items to be chosen.
How many permutations of 2 letters can be formed from ABCD?
4P2 = 4! / (4 - 2)! = 12.
How many ways to award gold, silver, and bronze medals in an Olympic event with 12 athletes?
12P3 = 12! / (12-3)! = 12 * 11
* 10 = 1320
How many ways can a committee of 3 members be formed from a group of 8 people?
12P3 = 12! / (12-3)! = 12 * 11
* 10 = 1320
What does the C++ function generatePermutations do?
It generates all permutations of a given vector of integers.
What is the purpose of std::sort in the generatePermutations function?
It sorts the array to ensure permutations are generated in lexicographical order.
What does the do-while loop in the generatePermutations function accomplish?
It iterates through all permutations of the array until no more permutations are available.
What does the C++ function std::next_permutation do?
It generates the next lexicographical permutation of a sequence.
What is the key difference between permutations and combinations?
In permutations order matters; in combinations
What is the formula to calculate permutations?;
Use the appropriate formula based on the problem context.
How many ways can 5 people be seated in a row of 5 chairs?
120 ways (5!).
How many different 3-topping pizzas can be ordered from 10 toppings?
120 combinations (10 choose 3).
How many possible 4-digit combinations are there if digits can be repeated?;
10000 combinations (10^4).
with repetition allowed?
17How many different codes are possible if a code consists of 3 letters followed by 2 digits
How many ways can a group of 4 students be chosen from a class of 15?
1 365 ways (15 choose 4).
