11) use the following definition of permutation below: List A is a permutation of list B if any of the following are true: • list A and list B are both null, otherwise a.head-b.head, and a tail is a permutation of b.tail a.head/b.head, and there exists a list C such that a.tail is a permutation of b.head:c, and b.tail is a permutation of a head:c a) Use induction to prove that any finite list is a permutation of itself-in other words, that the permutation relation is reflexive. b) Using the recursive definition of permutation above, use induction to prove that if list a is a permutation of list b, then list b is a permutation of list a-in other words, that the permutation relation is symmetric.

11) use the following definition of permutation below: List A is a permutation of list B if any of the following are true: • list A and list B are both null, otherwise a.head-b.head, and a tail is a permutation of b.tail a.head/b.head, and there exists a list C such that a.tail is a permutation of b.head:c, and b.tail is a permutation of a head:c a) Use induction to prove that any finite list is a permutation of itself-in other words, that the permutation relation is reflexive. b) Using the recursive definition of permutation above, use induction to prove that if list a is a permutation of list b, then list b is a permutation of list a-in other words, that the permutation relation is symmetric.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: Sets are collections (1) without defined order and (2) not allowing duplication. Multisets, also…

A: // Here's the implementation of bag-union and bag-intersection in Racket: (define (bag-union bag1…

Q: Write a function buckets : ('a -> 'a > bool) -> 'a list -> 'a list list that partitions a list into…

A: Write a function buckets : (‘a -> "a -> bool) -> 'a list -> ‘a list listthat partitions…

Q: Exercise 7. Write in pseudo-code a function that computes the height of a binary tree. Assume that a…

A: Pseudo code is an language independent representation of an algorithm.

Q: without defined order but which permit duplication, i.e., more than one element. We define the…

A: Given : sum : List × List -> ListThis function should take as arguments two lists representing…

Q: Function member of type" the list L. a list - bool so that member(e, L) returns true if and only if…

A: The Code of this given below.

Q: python code Write a recursive function such that, given a list of integers (say v) and an integer…

A: 1. find_subset(v, x)Input: A list of integers v and an integer x.Output: A subset of integers from v…

Q: Write a function to construct the union of two sets. -- Exercise 9 Hint: union (S1, S2) - the union…

A: The code for the above-given question is given below: Args: s1: An unordered list of elements…

Q: Let xHead, yHead and zHead be the head pointers of 3 linked lists of integers (called X-list, Y-list…

A: All the code already you have. I have implemented only merging the two list in third list so copy…

Q: A list is sorted in ascending order if it is empty or each item except the last one is less than or…

A: CODE IN PYTHON: def isSorted(inputList): if len(inputList) < 2: return True for i in…

Q: In [ ] Problem 3 Write a function buckets : ('a -> 'a -> bool) -> 'a list -> 'a list list that…

A: OCAML language : Object-oriented programming is possible with OCaml. According to the philosophy of…

Q: ce you to use recursion, you may not use the in operator. Rather, you should use recur ss s one…

A: Code 1: nlist = []def add(vals1,vals2):if len(vals1)==0 and len(vals2)==0:return []if len(vals1) !=…

Q: Sets are collections (1) without defined order and (2) not allowing duplication. Multisets, also…

A: Here's the implementation of bag-union and bag-intersection in Racket: (define (bag-union bag1 bag2)…

Q: a) Suppose the following recursive set S: • Basis elements: {0, 2, 4} • Recursive step 1: a, y ES I*…

A: Hey there, I am writing the required solution based on the above given question. Please do find the…

Q: Describe each of the following sets by listing its elements: a. {x | x ∈ N and x2 − 5x + 6 = 0} b.…

A: a. {x | x ∈ N and x^2 - 5x + 6 = 0} solve the quadratic equation x^2 - 5x + 6 = 0, factors as…

Q: The subset sum problem is stated as follows: Given a set S {a1, a2, a3, an }of n positive integers…

A: Answer: C++ Source Code: #include <iostream>using namespace std; bool sss(int S[], int num,…

Q: Rewrite the set of productions below in Extended Backus-Naur Form (EBNF).

A: Extended Backus-Naur Form : EBNF is a way to specify a formal language grammar. A formal language is…

Concept explainers

Types of Linked List

A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.

Linked List

When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).

Question

11) use the following definition of permutation below:
List A is a permutation of list B if any of the following are true:
• list A and list B are both null, otherwise
a.head-b.head, and a tail is a permutation of b.tail
a.head/b.head, and there exists a list C such that
o a.tail is a permutation of b.head:c, and
b.tail is a permutation of a head:c
a) Use induction to prove that any finite list is a permutation of itself-in other words, that the permutation
relation is reflexive.
b) Using the recursive definition of permutation above, use induction to prove that if list a is a permutation of
list b, then list b is a permutation of list a-in other words, that the permutation relation is symmetric.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1: Introduction

VIEW

Step 2: Proof for Part a

VIEW

Step 3: Proof for Part b

VIEW

Solution

VIEW

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Exercise 2 Define a function member of type 'a * 'a list -> bool so that member (e, L) is true if and only ife is an element of the list L.
Exercise 3D Write a function sundaram which implements this algorithm. You should check the results by comparing the final list to that produced by the sieve of Eratosthenes, and for the avoidance of doubt, the output of sundaram (5) should be [ 3,5,7,11].
Q3 Given a fairly common definition for a struct Node that can be used to make a singly linked list of int values: struct Node { int data; Node *next; } Q3.1 Write an iterative function printList (const Node* head) that takes a pointer to the head Node of the singly linked list and prints each value of the linked list, one per line. Write the entire function (including the function signature), and be sure to write correct and compilable C++ code in your solution. #include using namespace std; Enter your answer here Q3.2 Rewrite the printList (const Node* head) function from part 1 recursively. #include using namespace std; Enter your answer here
Define a recursive function named trim; it takes as its arguments a linked list (the head node of it) and a non-negative integer representing the index of an element in the list. The function mutates the linked list such that all elements that occur after the index is removed. Additionally, the function returns a linked list of all the elements that were moved. If the index value exceeds the length of the linked list, it should raise an IndexError. For example, if we defined a list as l1 = LN(1, LN(2, LN 3))) , calling the function would return the linked list LN(2, LN(3)), and the mutated l1 would become LN(1). You must use recursion. def trim(l: LN, index: int) -> LN:
Python help
4. Define a polymorphic function of type: shimmy :: [a] -> a -> [a] which takes an input list and another value (of the same type as the input list's elements) and outputs a list based on the input list, but where every element is preceded by and followed by the second input. For example shimmy [1,2,3] 0 = [0,1,0,2,0,3,0] and shimmy 0 0 = [0]
Define these functions in SML Language with using the standard functions abs and length, and the Int.toString function, Predefined functions: real, floor, ceil,round, trunc, ord, chr, str, hd, tl,explode, implode, and null dont use pattern matching to solve the function
Design an implementation of an Abstract Data Type consisting of a set with the following operations: insert(S, x) Insert x into the set S. delete(S, x) Delete x fromthe set S. member(S, x) Return true if x ∈ S, false otherwise. position(S, x) Return the number of elements of S less than x. concatenate(S, T) Set S to the union of S and T, assuming every element in S is smaller than every element of T. All operations involving n-element sets are to take time O(log n).
For Sob 22 - write up what the properties of sets, lists, vectors and strings are and whether they are mutable or immutable. Then consider the class of problems that they are best for. Use some code to illustrate your points. e.g. if you have a function that solves a problem using lists, then you can say why you can/can’t use vectors for it or sets etc. Based on dr racket. e.g.
Q1. Mark the following as True or False. Flow graphs can automatically delete common sub-expressions. The driver program for all the LR parsers is different. Dead code elimination technique deletes redundant code statements. Low-level intermediate representation is independent of the target machine. In relocatable machine language, subprograms are compiled separately.
Exercise 4 Define a function repeats of type 'a list -> bool so that repeats (L) is true if and only if the list L has two equal elements next to each other.
OCAML Code for the solution, Not python or another language.